I have a situation where I need to allow a user to pick from a set of available scopes in the Advanced Search box in SharePoint.  In and of itself, this is not a problem as I can configure the Advanced Search Web Part to do this and then customize the specified Display Group as needed.  Easy.  The problem arises when the user attempts to select multiple scopes in the Advanced Search and hits Submit.  Then I get:

“Your search cannot be completed because of a service error. Try your search again or contact your administrator for more information”

It turns out that the problem is that one of the scopes included in the Display Group contains the Scope Rule to include All Content.

The Solution

Create a new scope in your Shared Service Provider that will include all of the content via URL includes and such but does not have the All Content scope rule.  Then update the Display Group used for Advanced Search to use the new scope instead of the original scope. Naturally, the complexity of this option will vary greatly based on your environment.

Note: I cannot take credit for solving this as the original diagnosis and solution is posted here.  I'm rewording it and reposting it here in the hopes of making it easier for people to find as tracking down the original solution took quite a while.  The original solution is also rather technical which may cause non-technical admins to gloss over pretty quickly.