After update, Outlook search reports "We're having trouble fetching results from the server..." on every search

Here is what I tried, and got the search to work.

Ran Office Quick Repair - still saw issue after the repair

Created a new Outlook Profile, started Outlook with the new profile, and still saw the issue

Started Outlook again with my original profile, and the Search is now operating as normal.

Here is what I tried, and got the search to work.

Ran Office Quick Repair - still saw issue after the repair

Created a new Outlook Profile, started Outlook with the new profile, and still saw the issue

Started Outlook again with my original profile, and the Search is now operating as normal.

For me, the problem occurs with my default outlook.com account (and also an old hotmail.com account), but not my Microsoft 365 work account, IMAP, or gmail. 

The symptom is that Current Folder and Current Mailbox scope don't work, while Subfolders and All Mailboxes scope do.  (So I guess using those latter two scopes is a quick partial workaround.)

Changing profile didn't help. 

Turning off cached exchange mode avoids the problem, so I've done that for the moment. 

Update:  with cached exchange mode off, I'm not able to send outlook.com emails anymore - I get the mysterious "The operation failed.  The messaging interfaces have returned an unknown error".  So I've had to turn cached exchange mode back on.

Same. Only the "all Outlook items" search worked for me. still a hassle

Yes I am also having this issue - I haven't changed anything and it just started about a week ago.

This article makes me think it's an issue with FAST search: 

http://thewindowsupdate.com/2019/04/25/how-outlook-2016-utilizes-exchange-server-2016-fast-search/

I have the same problem since the recent update. Rebuilding local index didn't work - no surprise as the problem seems to be at server level. The workaround suggested on this thread is helpful - if I search all mailboxes it works. So to restate the problem:

* Search function has stopped working on This Folder or This Mailbox and always requires one of two workarounds:

   A - "look on this computer instead"

   B  - change scope of search to All Mailboxes and then server level search works

Either way - this means that the simple everyday function of looking up an email has become much more cumbersome since Microsoft moved the search box up into the top blue bar. I hope they fix it soon.