Problem: Outlook’s “instant search” isn’t returning any results, or search isn’t returning results unless you change the scope from its default Current Mailbox to something else.
Solution: (Well, more accurately One Potential Solution) Run scanpst.exe, found in the same folder as Outlook.exe. On my system that’s C:\Program Files (x86)\Microsoft Office\Office15.
Point the utility at your PST or OST files. It will scan them. If it finds errors, you’re offered the option to back them up (Duh!) before repairing.
Fixed up my search problems that had been nagging me for a bit too long…