The issue turned out to be related to Microsoft recently updated a certificate which requires on-premises Exchange deployments that have federated sharing configured to render the latest certificate version.
This only applies to hybrid deployments or cross-organizational deployments.
It turned out this particular environment hadn't picked up the change. So we had to refresh the certificate to ensure access to Free/Busy again worked as expected. We did this by running the following command in the on-premises Exchange environment.
Get-FederationTrust | Set-FederationTrust -RefreshMetadata
If you see a similar behaviour, I recommend you run the above command.