If your search function isn't finding any of your messages or only recent messages in the last two weeks, you may need to rebuild the search index. You may also receive a message "Instant search encountered a problem while trying to display search results. Modifying your query may resolve this problem" or "Outlook cannot perform your search."
- Choose File | Options | Search
- In the "Change the Outlook stores indexed by Windows Search", click Indexing Options
- Select Advanced.
- In the Troubleshooting section, select Rebuild.
- Select Close when finished.
- Click OK to close out of options.
This Microsoft support article has more detailed information on search issues and troubleshooting tips - https://support.microsoft.com/en-us/help/2769651/outlook-search-returns-no-matches-found