Hi,
Are your users using Exchange Accounts? Are they using their accounts in Cached Exchange Mode or Online Mode?
For these affected users, you may need to rebuild the Index. It might be that the Index itself has been damaged. In order to reset this, go to Control Panel-> Indexing Options-> Advanced-> button Rebuild.
This will rebuild the entire Index from scratch and depending on the amount of documents to be indexed, this could take quite long and degrade your systems performance while the Indexer is still busy. It is recommended to have it rebuild itself overnight.
Regards,
Melon Chen
TechNet Community Su