Hi all,
From the investigation of traces that samble provided the Outlook Service Team determined the root cause. The main reason that is causing search not to work is a configuration issue. I'm still trying to fully understand the issue before making any suggestions to mitigate so please don't make any changes without doing some testing.
The issue is happening because the email address used for the on prem Exchange mailbox is the same as the MSA account used to sign into Office. For example, the MSA addresses are listed on this page, https://account.live.com/names/Manage. If you check this page does it have the same email address that you have configured in Outlook? Or, does it match the email account that you have signed into Office (File, Office Account, User Information)?
What would address the issue is to create another MSA address Alias and to delete the current one that matches the On Prem address (do not do that right away). This would change how you sign into Office. I don't have this configuration to test but I would first check if it is possible to workaround the issue without removing the current email address MSA that you have. For example, I would test creating another Alias at https://account.live.com/names/Manage and trying to use that to sign into Office. It may be necessary to make the new MSA address the Primary Alias but I am not sure. For now I would avoid deleting any Alias. Also, I know from personal experience that you can only change the Primary Alias two times in a week.
Initially, can someone review what I have explained and check it and see if it matches your scenario? Are there any other issues you know of that removing the matching email address to on prem email address alias would cause any issues?