I had a customer who had several users who could not do any searching in Outlook. The error was, "Something went wrong and your search couldn't be completed." along with a mention of the appearance of there being no network connection.

Another engineer had been talking with one of the customer's IT people about a different issue and apparently they may have accidently turned off EWS (Exchange Web Services) globally while investigating/troubleshooting another problem. I compared the broken mailbox to a known working mailbox and the working mailbox had EWS enabled, so I re-enabled it using some Powershell commands and the user was now able to search. 

To check if EWS is enabled/disabled - get-casmailbox someMailbox@domain.com | fl *ews*

To turn on EWS on for Outlook - Set-CASMailbox someMailbox@domain.com -EWSEnabled $true -EWSAllowOutlook $true

https://docs.microsoft.com/en-us/powershell/module/exchange/client-access/set-casmailbox?view=exchange-ps

Exchange Web Services is typically on by default for Outlook as it is used for a variety of functions including searching, calendar shares, permissions and availability, shared mailbox permissions, and out of office settings.