I can confirm that Outlook Version 16.58 (22010406) resolves this issue.

Microsoft confirmed this issue: https://support.microsoft.com/en-us/office/search-in-outlook-for-mac-returns-no-results-after-installing-macos-monterey-12-1-075c5f09-35db-4205-aba3-eea2f168c71b

Same issues after upgrading to macOS Monterey 12.1. I installed Outlook for Mac beta Version 16.57 (21122200), but the issue is still there. Rebuilding Spotlight database does not help, Outlook still shows "no results" when searching.