"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?"
Correct.
"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."
I have nothing in my firewall policies that would block access to my on-premises.
"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."
user A cannot connect to ANY free/busy on premise, but user B can connect to ALL free/busy on premise. I understand your point that user A could be on a different exchange server inside Office 365, but why would that one server not work whereas the others would when I am not blocking any traffic? I could set the TargetSharingEpr in both directions, but why would that fix the issue just for user A?
Thanks so much for your response!