Following an issue with Free/Busy in Exchange online, earlier this week, I was troubleshooting the exchange of Free/Busy information in some of my hybrid deployments as Free/Busy information was still not working.
After having checked some (obvious things) like the Organization Relationships and whether or not Autodiscover was working properly, I discovered an issue when running the Test-FederationTrust cmdlet.

In fact, the cmdlet completed almost entirely successful, except for the very last step in the process:

Id         : TokenValidation
Type       : Error
Message    : Failed to validate delegation token.

This also explained why I was seeing 401 Unauthorized messages when running the Test-OrganizationRelationship command.

I then checked the same in some of my other deployments and found out the all had the same issue. At least, there was some common ground to start working from.
I turned to co-MVP Steve Goodman and asked him to run the same command in one of his labs in order to have a point of reference. At the same time, he asked me to run a command which might help:

Get-FederationTrust | Set-Federationtrust –RefreshMetaData

After running the command, I re-ran the Test-FederationTrust command which now completed successfully.

Conclusion

Although the Free/Busy issues in Office 365 should be solved, some customers might still experience problems exchanging Free/Busy information. In this case, the problem manifests itself by e.g. online users not being able to request on-premises user’s availability information.