Seriously though, I always have problems with Outlook search.
At least you only have problems with the search. Since the last release, my Outlook doesn't even connect to the Exchange server at all. I have to use fucking IMAP, which defeats the whole purpose of Outlook. And as an additional bonus, replies sent from another computer sometimes won't show up in Outlook, despite being saved in the correct folder.
Outlook 2016 is a buggy piece of shit and should die in a fire.