Outlook search stopped working

Two to three days ago my Outlook suddenly stopped returning any search results. Every time I search I get this message. (I am using New Outlook). I have tried changing browser, changing comput...