Rebuild the indexes. In EMC, navigate to your Exchange scripts folder. Run the following script on each of your databases. This can be done while live.
Exchange Scripts folder- .\resetsearchindex.ps1 {DBNAME}
Stops the search service, deletes files, starts service