The Outlook 2013 client will not find results when performing a search, or it has issues when attempting to search.
To resolve the issue, please follow the steps below to re-build the Outlook Index.
1. Click on File > Options;
2. Select Search in the menu on the left, then click Indexing Options;
3. This will open the 'Indexing Options' window, click Advanced;
4. Click the Rebuild button in the advanced options;
Outlook will then rebuild its search index. This can take a while to complete, but you can continue you use Outlook as the process runs in the background.
If the above solution does not resolved the issue, your Outlook profile will need to be re-created. Please see this guide that shows how to do this.