I contacted support and got the following reply:
We have noticed this issue experienced by few of our users and this has been reported to our Development Team. I understand the severity of the issue and the requirement for the resolution. Since this needs to be tested and the fix needs to be rolled out, we would not be able to provide an ETA on the fix.
Fix for any BUG filed with Outlook will be rolled out through "Updates". So we suggest you to keep your Outlook up to date. You may also refer to the Microsoft blog, where all the updates to the latest features and fixes are announced -
https://docs.microsoft.com/en-us/officeupdates/release-notes-office-for-machttps://support.office.com/en-us/article/Fixes-or-workarounds-for-recent-issues-in-Outlook-for-Mac-54afa5e3-db38-422a-9d94-3b55330ded8e/As a workaround, you can manually open the advanced search in Outlook for Mac, by clicking on Search bar on the top right corner then, in the search ribbon click on Advanced. See if it works.