The user uses 2 different iPhones 12 (Mini and Max). He uses the same account associated with the company's MS Exchange 2016 server on both. On one iPhone, Outlook (older Outlook version 4.2148.0) searches for emails, contacts, and calendar events by keyword. The other iPhone (last Outlook version 4.2216.0) with the same expression only searches for emails and contacts, but does not search for anything in the calendar.
We went through all the settings in Outlook and iPhone (Search and Siri settings) - everything looks to be set up exactly the same.
If both are connected to another Exchange 365 test account, the Outlook Calendar search works on both iPhones. But calendar search doesn't work with company's Exchange 2016 account (even on another newly installed test iPhone with the same account).