Search in Outlook 2016/2019 still broken (May 2020)?

[German]Since the beginning of May 2020, some users of Microsoft Outlook are having a broken search function. Microsoft rolled out a fix for this the problem, but this does not always seem to work. Here's a summary of the feedback I've received in the blogs so far.

The Problem

Users told me in comments about the problem that the search in Outlook no longer works. I had mentioned it within the article Outlook Search broken since last Update, Fix available? It is important that the issue refers to the click-to-run variants of Office (so probably Office 365, Office 2016 / 2019).  

In this article there were then two additional pieces of information. First, a fix for the error was announced by Microsoft. And I had specified a workaround (disable server-based search to search locally, see also this German comment). The English and German articles got a lot of feedback.

Microsoft rolls out the fix

On May 21, 2020, blog reader Rachel posted a comment with the following status information from Microsoft:

UPDATE:

Status: We've confirmed that the deployment is now complete. In order to resolve the issue, users must restart Outlook desktop client twice to have their search features return to normal functionality. We're going to continue monitoring service health for 24 hours to ensure no further issues occur.
Next update by: Friday, May 22, 2020, at 1:00 AMUTC; PublishedTime=2020-05-20T23:28:30.757

Gave mixed feedback on it. Kate made the observation that most of her customers reported the problem after upgrading their OnPremise Exchange Server (2016) to CU16.

Blog reader Rachel later added in this comment that the fix announced in the status report only helped in Office 2019. Nothing happened with the Office 2016 installations. Microsoft is trying to fix the bug, but this has not been a resounding success. 

In the channel announcements I only found an entry from May 21, 2020 in the English language version, but this does not mention the search. Since May 16, 2020 there is this Microsoft Answers forum thread about the bug. On page 2 you can find the workaround 'change scope of search to All Mailboxes and then server level search works', which seems to help. But there is no solution from Microsoft (yet).

It works, or even doesn't work (anymore)

In this German comment blog-reader Marc wrote the following text on 18 May 2020:

Problems have suddenly disappeared. Everything works again when searching with Exchange Cache Mode and without office updates. My version 2004 (Build 12730.20270).

But today the following Windows updates were installed:
KB4552931 and KB4556799

The change log for KB4556799 contains the following sentence: "Updates to enhance security when you use Microsoft Office products".

In follow-up comments, however, there is feedback that it didn't help or that a downgrade solved the problem. The last comment from German blog readers sounds even crazier:l

So after it worked for four days without workaround after the Windows updates, the search in the whole network does not work anymore. Neither Office nor Windows updates were installed!

Summarized: Search does not work in the whole network, again, again, again, again. No workarounds, Windows and Office at current Microsoft status.

What are your observations? Has anyone found a working solution or even a cause?

Similar articles:
Microsoft Office Patchday (May 5, 2020)
Probleme mit der Outlook-Suche seit Update, Patch da? 
Outlook Search broken since last Update, Fix available?