Exchange 2016 CU8, when installed in hybrid mode, has a free/busy issue. This issue occurs when mailboxes are present both on-premises and in the cloud . A free/busy query from Office 365 to on-premises will fail for cloud-based mailboxes if those mailboxes do not have an archive enabled. The problem occurs because OAuth connectivity fails.
For Office 365 users who have an archive enabled, this problem does not occur. The obvious workaround is to enable an archive for the cloud-based mailboxes.
If the workaround is not acceptable, an IU (Interim Update) is available from Microsoft CSS for this problem. The problem should be corrected in Exchange 2016 CU9. The KB describing the IU is KB4058297. The IU is available at no charge if you cannot wait until the release of CU9.
Follow me on twitter: @EssentialExch