This Blog Post refers to Exchange 2007 and Exchange 2010. In Exchange 2013 we replaced the Indexing Engine and also the Search Engine so this does not apply for now.
In many support cases we have seen issues when not all items are being indexed and as a result also not all are being found by Users performing a search.
Taking advanced traces and checking the Source code we have seen that in some cases when Items are indexed, or are trying to be indexed, we try to contact the crl.microsoft.com URL and fail. This can have multiple reasons depending on topology and proxy / firewall configuration.
In these cases we recommend creating a hosts file entry that looks like :
Another thing that does the trick ( next to the crl.microsoft.com entry ) is another entry :
Where “domain.com” is your domain.
This is something related to Web Proxy Automatic Discovery, I won’t go into deeper details though.
This should solve the above described issue. Maybe a restart of the MSExchangeSearch Service is also needed.
If this doesn’t help, you may have to rebuild the whole Index following the following article:
How to Rebuild the Full-Text Index Catalog :
We recommend doing this only after business hours as rebuilding the Index Catalogs will perform a full crawl on all the mailboxes on the Databases you chose and this is consuming a high amount of CPU being able to cause performance issues on the specific Servers.