Setting up a hybrid configuration between Office 365 and on-premise Exchange may seem straight forward, but there are a lot of pitfalls to tackle. One of the more frequent issues is a problem with free/busy information not being visible, or the inability to migrate mailboxes from/to Exchange Online.

Additionally, you may have received this error during the initial configuration of the hybrid setup:

Hybrid Configuration Wizard

Office 365 was unable to communicate with your on-premises Autodiscover endpoint. This is typically due to incorrect DNS or firewall configuration. The Office 365 tenant is currently configured to use the following URL for Autodiscover queries from the Office 365 tenant to the on-premises organization https://autodiscover.contoso.com/autodiscover/autodiscover.svc/WSSecurity. See the following article for further information: http://go.microsoft.com/fwlink/p/?LinkId=275838.

Obviously, this error message did not really contribute to as to what exactly the problem could be. When running the Exchange Remote Connectivity Analyzer from Microsoft, there were no problems reported, so technically, everything "should" work!

After careful reviewing the situation with someone from Microsoft, they asked me to run a test of the organization relationship using Powershell's Test-OrganizationRelationship. The output of the cmdlet revealed another error:

STEP 3 of 4: Requesting delegation token from the STS…

RunspaceId  : 2a0844db-1337-4b35-993b

Identity    :

Id          : AutodiscoverServiceCallFailed

Status      : Error

Description : The Autodiscover call failed.

IsValid     : True

ObjectState : New

Terminating execution. Autodiscover service call failed.

Again, we already knew this, but still no real reason as to why it would fail. So, I started googling and came across this article, where the author tried an iisreset on the on-premise Exchange servers.