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 Advanced 
  

• Click the Rebuild button 
  

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.