Demystifying Hybrid Free/Busy: Finding errors and troubleshooting

Let me see if I understand this: You have user A in EXO and user B in EXO, if user A queries F/B for user C in Exchange on-premises, we get an autodiscover error for the user C's email address? But if user B queries F/B for the same user C in Exchange on-premises, we get success?

If that is the case, I assume that user A's EXO mailbox server uses a different Outbound IP that is not allowed to connect to your on-premises, but user's B mailbox server outbound Ip is allowed to connect.

If user A and user B are not querying the same user (user C), then check the external email address and properties of the target user C in Exchange Online, make sure the external email address of the on-prem mailbox's domain is on the IntraOrganization Connector's Domains and make sure DiscoveryEndpoint is correct, pointing to the correct Autodiscover. You can also bypass Autodiscover by setting TargetSharingEpr in Exchange Online Set-IntraOrganizationConnector.

For privacy reasonse, in your comment, please remove the IP:443 that points to your on-premises org.