Outlook 2016 and Mac OS incompatibility - multiple episodes of loss of search functionality [duplicate]
Outlook searching relies on spotlight indexing. I would start with ensuring that Sys Prefs - Spotlight - Privacy is empty. You can rebuild the index with the below steps. As a sidebar perhaps this is part of the reason why it's randomly losing results: https://eclecticlight.co/2019/08/02/spotlight-search-can-skip-files/
Open Terminal and run:
sudo mdutil -i off /
sudo mdutil -i on /
sudo mdutil -E