Oh my goodness! This has been a huge pain for us for over a month now. We have tried reindexing Spotlight, toggling to the "new" outlook, switching outlook over to offline and then back to online, deleting our 3 email accounts (2 POP & 1 Gmail) and then adding them back . . . seriously every single solution we have tried. But, NOW it is FINALLY working!
Outlook 365 version 16.61 (you might need to click "Advanced" and on Update Channel, select "Beta Channel")
MacOS Monterey 12.3.1
My Search and Unread Filters in Outlook are now FINALLY working!