This problem occurs because expensive Transact-SQL queries are generated in this search scenario.
To resolve this problem, install hotfix 950280.
For more information, click the following article number to view the article in the Microsoft Knowledge Base:
950280 Description of the SharePoint Server 2007 hotfix package: March 21, 2008
Hotfix post-installation information
After you install the hotfix, the Advanced Search page does not display the Contains and Does not contain operators under the Search by properties section. This prevents users from creating expensive queries unintentionally.
To specifically enable the Contains and Does not contain operators, follow these steps:
On the Advanced Search page, click Site Actions, and then click Edit Page.
On the Advanced Search Box Web part, click Edit, and then click Modify Shared Web Part.
Expand the Properties tab.
In the Properties text box, locate the following xml entry:
<Option Name="AllowOpContains" Value="False"/>
If this entry does not exist, create the following entry:
<Option Name="AllowOpContains" Value="True"/>
If the entry already exists in step 4, change “False” to “True."
Note To disable these options, you can change the text back to “False."
Click Publish to publish the page.
Microsoft has confirmed that this is a problem in the Microsoft products that are listed in the "Applies to" section.