Last week we had a strange case logged at our helpdesk. After a customer migrated from Exchange 2007 to Exchange 2010, he seemed to be unable to search for items prior to the migration in his mailbox. If he for example did a query on the word ‘news’, only item received after the migration would show up in the search results. Items prior to that would be visible in his mailbox, but would not show up in the search results.
The problem seemed to be also depended on which datastore the mailbox was located. Mailboxes on datastore one had the issue, but mailboxes on datastore two seemed fine.
Digging deeper we found out that the folder where Exchange is storing its indexing data, was quite small for datastore one compared to datastore two.
Datastore 1 was around 62 GB, with the size of the indexing folder being around 700MB.
Datastore 2 was around 23 GB, with the size of the indexing folder being around 2.3 GB.
We started to look for a way to rebuild the entire index, but before we did this we moved a mailbox from store one to store two. After the move searching seemed to be working again.
On technet (http://technet.microsoft.com/en-us/library/aa995966(EXCHG.80).aspx) we found this article that explains how to rebuild the index from scratch.
Following commands should be performed on the server where the database is located.
The catalog data can usually be found in a path which looks like D:\\CatalogData-
You can also use an Exchange powershell command to find the catalog location of all the stores hosted on this server.
GetSearchIndexForDatabase -All
You can usally find this script in the folder C:\Program Files\Microsoft\Exchange Server\V14\scripts
You should get something like this.

Now these are the folders we will need later on.
Now, stop the Exchange Search service with the following command.
Net Stop MsExchangeSearch
Delete or rename the CatalogData folder of the Database which needs to be reindexed.
Now start the Exchange Search service again.
Net Start MsExchangeSearch
You will see the folder getting recreated, and it should start to grow in size. Note that it can take a while before your index is completely rebuild.
After performing these actions, searching for mails in datastore one prior to the migration worked again. What went wrong in the first place is still a mystery though