I was recently looking to perform a search of a mailbox containing keyword items, on performing this using the Search-Mailbox cmdlet, this would immediately fail with the following application error for the source MSExchange Mid-Tier Storage, with the Event ID 3003:
Search 'SearchStatus\e21eb91d-050a-4a5d-be1f-a10349672425' has following error: An error occurred when searching *****. The message is 'Try using fewer keywords at the same time, reducing the number of users in the From, To, Cc, and Bcc fields, and reducing the number of mailboxes that are searched at the same time. When you use wildcards, make search queries as specific as possible. For example, if the search query used short words with one or more wildcards (for example, pat*), a large number of words or phrases may be returned because all words that start with "pat" are searched. Search failed on mailbox '*****\*****\bd0b6335-1f83-42c9-9c2c-949092d6515e'.
My initial search filter was for a single mailbox with a single keyword, so this would not apply to using either fewer keywords of users!
I found an article on the how to rebuild the Full-Text Index Catalog at http://technet.microsoft.com/en-us/library/aa995966%28EXCHG.80%29.aspx.
By invoking the below, this allows you to rebuild the Full-Text Index Catalog Using the ResetSearchIndex.ps1 script, for all mailbox databases:
%ProgramFiles%\Microsoft\Exchange Server\v14\Scripts\ResetSearchIndex.ps1 -Force -All
Or to rebuild the Full-Text Index Catalog for a single mailbox database:
%ProgramFiles%\Microsoft\Exchange Server\v14\Scripts\ResetSearchIndex.ps1 -Force %Mailbox Database Name%
You may also perform this step manually, by stopping the Microsoft Exchange Search Service and deleting the full-text index catalog directory for the mailbox database. You can determine the catalog directory for all mailbox databases by invoking the following:
%ProgramFiles%\Microsoft\Exchange Server\v14\Scripts\GetSearchIndexForDatabase -All
The Exchange Search Indexer will now create a new search index and perform a full crawl of the database, which will create an information message for the Event ID 109:
Exchange Search Indexer has created a new search index and will perform a full crawl for the Mailbox Database ********** (GUID = d06d1893-f282-4443-a0f3-bedac80c7cd6). Reason for full crawl: Catalog doesn't exist.
On completion, this will create an information message with the Event ID 110, to which you should be allowed to run the Search-Mailbox cmdlet against multiple mailboxes and keywords
Exchange Search Indexer completed a full crawl (indexing) of Mailbox Database ********* (GUID = d06d1893-f282-4443-a0f3-bedac80c7cd6).
Deans Blog 