My config:
MacOS Version 12.1 Monterey
Microsoft® Outlook for Mac Version 16.56
I thought Outlook search wasn't working at all.
It turned out it was working VERY, VERY SLOWLY. (We're talking several minutes of looking at NO RESULTS before something happens. There is no progress indicator! 😡)
What worked for me was:
From Finder, open the Applications folder.
Ctrl+click or right-click Microsoft Outlook,
Select Show Package Contents.
Open Contents > SharedSupport
Launch Outlook Profile Manager.
Select the profile that you want to remove (There is probably only one and it's quite safe to delete. When you restart Outlook below it gets recreated.)
Delete (the minus sign '-' at the bottom beside the '+') the selected profile
Restart Outlook
Add your profile when Outlook prompts you
Start your search
Grab a coffee and a good book ...
And, if you need a search result quickly, you can get it fast using the web version of Outlook at outlook.com.