We had an issue where people searching in Outlook 2019 would get a "Something went wrong and your search couldn't be completed. It looks like there's a problem with your network connection." error. All network tests through Outlook succeeded, all updates installed, we recreated Outlook profiles, disabled cached Exchange mode, and reinstalled Office. Nothing worked. I came across a TechNet thread that suggested a registry fix, and that worked great.

HKEY_CURRENT_USER\Software\Microsoft\Office\16.0\Outlook\Search

Value name: DisableServerAssistedSearch 
Value type: REG_DWORD
Value: 1

Hopefully that'll help someone in the future!