Suddenly all users unable to search from Outlook 365

[m0bov]

Hi all, we have Exchange 2016 here, Outlook 365 on the desktops. Suddenly now, everyone gets the prompt "something went wrong and your search could'nt be completed". You can click on "Let's look on your computer instead".

 

Its appears on everyone's desktop so its not a local issue. Before I bounce the server, any ideas?

 

James