I had the same issue after using migration assistant in moving my system from an iMac Pro to the Mac Studio. iOS is Monterey 12.4. Outlook is version 16.64. Nothing worked until I decided to wipe the Studio clean and start a fresh re-install. This time I did not use migration assistant during the setup process of the Studio. I got the iOS up and running and setup my Apple ID/iCloud account. Then once the system was installed, I ran migration assistant and transferred my user account over just like before. But this time the Outlook search is working. It's still indexing but I am getting results for more common search terms. Hope this may help someone else out with this frustrating problem.