Hello Nenad Milanovic,
According to your description, I would like to confirm with you the detailed version of Exchange CU and Outlook.
In addition, searches may be affected by how you add a shared mailbox in Outlook, so how do you add a shared mailbox? Was it added as an additional email account or auto-mapping?
Besides, you can try to disable FAST search either by applying Group Policy or by implementing the DisableServerAssistedSearch and DisableServerAssistedSuggestions user registry values.
Group Policy registry path:
HKEY_CURRENT_USER\software\policies\Microsoft\office\16.0\outlook\search
DWORD: DisableServerAssistedSearch
Value: 1
Reference: How Outlook 2016 utilizes Exchange Server 2016 FAST Search
If the issue persists, it’s suggested to try turning off cache mode for shared folders:
File tab -> Account Settings -> Double-click the account name -> More Settings -> Advanced tab -> Clear the check mark from download shared folders.
Hope the above information is helpful to you.
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.