Applies to the error:

If Outlook is not searching all of your email correctly, you can rebuild the Outlook search index to fix this:

  • Click on File then Options

  • Select Search on the left then click Indexing Options 
    Click Search then Indexing Options

  • Click Advanced 
    Click Advanced

  • Click the Rebuild button 
    Click Rebuild

This will cause Outlook to rebuild its entire search index. This can take a long time to complete but you can continue to use Outlook and it will do this in the background.