same experience with MBP 13" M1 running 12.1 and OL 16.56 (21121100) with mailbox on on-prem Exchange server. Worked until recently when I started to notice that the search results were not showing all possible results. gone through all the common steps to re-index. bad idea. as others already noted, the index is there - try spotlight search using "kind:message "searchterm*" - and right after re-indexing a first search seems to find results but any subsequent searches only return "no results". read in other forums that the the issue would affect mainly users of on-premises Exchange as for Exchange Online there would be a newer OL version which doesn't have the same problem. likely the issue boils down to MS sunsetting EWS 03/31/2022 with never versions switching to REST and GRAPH API https://office365itpros.com/2021/10/11/api-deprecations-signal-demise-exchange-web-services/ MS support suggested to re-assign OL as the default handler for .EML files but no joy. final response was Yes, we are aware of this issue. We had similar problem with Big Sur update previously which was fixed with another patch update from Apple. Our backend team are working together with Apple regarding this concern. This might take sometime but the fix needs to come through Apple so for the moment I'll resort to using Outlook Webmail where searching works very well

thought Outlook "old" and Outlook "new" were two distinct software packages. turns out it's the same! you can switch it by going to the "Outlook" menu. reverting my beta-channel OL 16.58.22011705 it re-gains it's capability to work with Exchange Server on-premises AND showing a working index :))