Microsoft
It's happening across multiple builds in our environment ranging from v2004 to v2007. I have found other threads on the internet which state people are randomly seeing the same behavior. We know it's not the Exchange index as search works from OWA. Here are some example threads:
https://community.spiceworks.com/topic/2201491-outlook-2016-2019-search-workaround-microsoft-un-resolved?page=1
https://www.reddit.com/r/Office365/comments/ihop87/error_searching_on_online_archive/
What makes this difficult is that you can login into a machine and not have an issue, then login to another machine and possibly have the issue. The only common denominator between machines and other organizations is the Outlook client, so it seems like some bug.
I turned on Advanced Logging and see that this error is thrown:
Search query 1: Problem: ServerRequestFailedOther Detail: HRESULT: 80004005. HTTP Status: 200. Error: . TraceID: Error Message: 407b10e7-1ae2-4c74-b05f-553d95c50181 Problem: ServerSearchAlgorithmFailure Detail: HRESULT: 80004005. Function: CSearchPagingManager::HrCreateSearchRequestAndExecute Error Message: General error encountered in server search algorithm
