A few times a year a user complains that searching trough his mailbox is not accurate.
Rebuilding the Exchange Search Index will usually solve this.
There is a default PowerShell script to reset the Search Index.
Open the Exchange Management Shell and navigate to %PROGRAMFILES%\Microsoft\Exchange Server\V14\Scripts and then run the following command:
.\ResetSearchIndex.ps1 -force -all
This will stop the MSExchangeSearch service and delete the catalog data for all mailstores.