Problems with Free/Busy from O365 to on-premises users

I was recently working on a customer solution with Exchange 2013 configured in a hybrid setup with Office 365.  I was having issues with free/busy requests from Exchange Online mailboxes to on-premises mailboxes.

Here is a description of the problem and the eventual resolution which took a few days and late nights to resolve:

Scenario

With a recent deployment of Exchange Server 2013 CU6 in a hybrid configuration with Office 365 user that had mailboxes on O365 couldn’t query for free/busy of on-premises users.  Users with on-premises mailboxes could query the free/busy status of O365 mailboxes.  The free/busy test for Office 365 in the Exchange Remote Connectivity Analyser (http://exrca.com ) showed the test for free/busy queries from O365 to on-premises as working successfully.

Environment

·        A multi-domain Active Directory forest with all DCs running Windows Server 2012R2

·        A single Exchange Server 2013 CU6 server with Mailbox/CAS roles installed, running on Windows Server 2012R2

·        DirSync and ADFS running on Windows Server 2012R2

·        Exchange Hybrid configured by running the hybrid configuration wizard on the Exchange Server 2013 CU6 server

·        Clients running Windows 8.1 and Outlook 2013 SP1

·        Clients running IE11 and connecting to OWA on the O365 portal