This is hilarious. Outlook cannot find emails because it uses Windows Search which is totally useless. Here's how to fix this - disable Windows Desktop Search Service for Outlook:
1. Open Registry Editor
2. In "Computer\HKEY_LOCAL_MACHINE\SOFTWARE\Policies\Microsoft\Windows" create new key "Windows Search"
3. In the "Windows Search" key create new DWORD value, name it "PreventIndexingOutlook" and set it to 1
4. Exit Registry Editor, and then restart Outlook