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?