I am in the process of moving a large Internet-facing website on MOSS 2007 from one hosting company to another. There are three main Web Applications (Apps A, B and C), each served by its own Shared Services Provider (SSP A, etc.). Two of the SSPs have custom search Scopes.
After the Site Collections had been configured and the web content migrated into them, I was finding that any search, in any of the three Site Collections, returned in the error message in the title above.
Web searches turned up a lot of advice on overcoming this ScopeNotFound Exception while developing custom search applications, but this was happening in the out-of-the box search pages.
Web Applications not associated with the right Shared Service Providers
I found the answer by checking the Associations under Shared Services Administration in SharePoint Central Admin: by accident, all three of the Web Applications had been associated with SSP ‘C’ (the default). I moved App ‘B’ to SSP ‘B’ and so on, and all searches immediately started working.