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!