I know the situation, Your are using OWA, ActiveSync or Outlook (in online mode) to search for an old email. Your search request only returns new emails even though  you can browse old emails. Now there is a good chance that mailbox database index has gone corrupt. You could do a check by running Test-ExchangeSearch but this might not return an error even though the index is corrupt.

What can I do to fix this problem?

My solution to this is to remove the index for the affected database and have Exchange rebuild it. Remember that this will affect all mailboxes contained in the database.

1 . Stop the service named “Microsoft Exchange Search”
2. Locate the database folder and delete the subfolder named some long file name containing letters and numbers. This first parts of the folder name is the GUID of the database. You could get the database by using this simple PowerShell command : get-mailboxdatabase <databasename> | ft name,guid -autosize

This step is particularly useful when there are multiple databases contained in the same folder.

3. Start the “Microsoft Exchange Search” service and wait.
Now we will have to wait for Exchange to rebuild the index. Remember that this could take a while depending on database file size. I prefer to do this a night.