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:
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.