If you’re getting the irritating “We couldn’t find what you’re looking for” error, it can be frustrating to fix.
Ultimately I had to fix the problem from outside of Outlook. I went to my “Change how Windows Searches” option dialog and rebuilt the index. I tried the exact same thing from inside Outlook but nothing ever happened.
Important: Before getting this to work, I also removed Outlook as an indexed location, restarted my PC, and then re-added it. However, this only partially helped, and there was still stuff missing from the index.