Issue

Outlook 2010 search shows below warning and doesn’t return any recent emails in the search results.

Search results may be incomplete because items are still being indexed. Click here for more details.

Indexing status shows number of items than need to be indexed and that number slowly increases. It looks all new items go into indexing queue but never get indexed.

Resolution

After a bit of digging I found that the issue was introduced by a recent Windows 7 Update. Specifically KB4022719 (Monthly Rollup). Until Microsoft provides a fix via another update (they already acknowledged the issue), I removed Outlook from Windows Indexing service. This makes Outlook search slower, but they at least it works. Other option would be to uninstall the update, but because this only affected small number of machines and workaround was acceptable, I decided to wait until Microsoft fixes this properly.

To remove Outlook from Windows Indexing go to Outlook > File > Options > Search > Indexing Options > Modify and remove checkbox next to Microsoft Outlook. For changes to take effect restart MS Outlook.

June 2017
Microsoft Outlook 2010
Windows 7 Pro