Same issue as everyone else. MacBook Air 13" M1, macOS 12.1, Outlook 16.55, and now 16.56. Have actually seen a search starting to populate as re-indexing (high MDS task seen in Activity Monitor), but then Search stops altogether.
As stated in another thread by a user:
The curious thing was that after I followed all steps above and when it was actively reindexing, I searched in outlook and it was pulling results!!! HOWEVER, as soon as it finished indexing the search immediately stopped working again."