Migration Exchange 2016 to 2019 then SE

Is this problem also happening when using OWA?

There are many workarounds within the article aswell as the comments. Have you already tried the following?

Just found a working Workaround to this problem.

exchange cache mode in outlook MUST be disabled.

after that you need to go to registry and delete the following key:

HKCU\Software\Microsoft\Office"version"\Outlook\Search

and search for the key where *.ost is the name.

delete this key while outlook is open (it didn't worked for me when outlook was allready closed)

after deletion restart outlook and search is working again.
how what where. i really don't know but untill MS comes with a solution this could achieve your goal.

Furthermore: Are those mailboxes very large mailboxes with 100k+ items or all mailboxes, even small ones?