Symptoms
After you install Microsoft Exchange Server 2016 Cumulative Update 8 (CU8), free/busy queries from Microsoft Office 365 users to on-premises mailboxes in hybrid environments fail if the cloud mailboxes are not archive-enabled.
Cause
This problem occurs because of a known issue that affects OAuth connectivity in Exchange Server 2016 CU8.
Workaround
To work around this issue, create personal archive mailboxes for each cloud mailbox.
Resolution
To fix this issue, install Cumulative Update 9 for Exchange Server 2016 or a later cumulative update for Exchange Server 2016.
More Information
To verify that you are experiencing this issue, use the Test-OAuthConnectivitycmdlet.
For example, connect to Remote PowerShell to Office 365 and run Test-OAuthConnectivity -Service EWS -TargetUri https://<On-Premises EWS URL>/ews/Exchange.asmx -Mailbox <Cloud Mailbox>
If your scenario is a match, this cmdlet will generate the following response:
Exchange Response Details:
HTTP response message: Exception: System.Net.WebException: The remote server returned an error: (500) Internal Server Error. at System.Net.HttpWebRequest.GetResponse() at Microsoft.Exchange.Monitoring.TestOAuthConnectivityHelper.SendExchangeOAuthRequest(ADUser user, String orgDomain, Uri targetUri, String& diagnosticMessage, Boolean appOnly, Boolean useCachedToken, Boolean reloadConfig)Status
Microsoft has confirmed that this is a problem in the Microsoft products that are listed in the "Applies to" section.
References
Learn about the terminology that Microsoft uses to describe software updates.