Using classic Outlook for Windows in business environments
Thanks Jayden, found it myself in the meantime!
It did work a few months ago, and the timing matches: my mailbox was moved from Exchange 2013 to Exchange 2019. Since then Outlook gets the suggestions from the server (EWS GetSearchSuggestions), and the server only remembers searches done in OWA. Searches in Outlook desktop never end up there.
The fix was this registry value:
HKEY_CURRENT_USER\Software\Microsoft\Office\16.0\Outlook\Options\Search
DisableServerAssistedSuggestions (DWORD) = 1
Restart Outlook and it manages the search history itself again, like before. New searches show up right away.
Important: the same value under ...\Outlook\Search (without "Options") did nothing for me. It has to be under Options\Search.
Hope this helps someone else.