Update: Upgraded the MS Outlook for Mac from 16.56 (21121100) to 16.58 (22010406) on Beta Channel and the Email search results in Outlook works like a charm! Thanks.

@SMR9999 Beta for Microsoft Outlook for Mac i.e., Outlook 16.58 (22010406) and not Monterey.