Demystifying Hybrid Free/Busy: what are the moving parts?

epeterson79 , sorry I missed it. There are a few things here:

1) Make sure that you are looking at the right Cloud Organization Relationship, that is meant for on-premises organization, should be Office 365 to on-premises.

In EXO PS:

Get-OrganizationRelationship "O365 to on-premises*" |FL Identity, DomainNames, Enabled, Free*, Target*

2) DomainNames should be your Vanity Domains, like contoso.com. No other MS domain like domain.mail.onmicrosoft.com or domain.onmicrosoft.com where Autodiscover for it always points to Office 365 servers.

3) Autodiscover for Contoso.com in Hybrid deployment must point to on-premises Exchange Server. So make sure you don't have a CNAME record for autodiscover.contoso.com that points to autodiscover.outlook.com. 

4) Assuming you have a Get-FederationTrust on-premises, you can put that ApplicationURI in the Cloud Organization Relationship and also if you have Autodiscover pointing to cloud for your contoso.com domain, then you can set TargetSharingEpr to point to the onpremises EWS url to bypass it.

Example of command in EXO PS:
Set-OrganizationRelationship "O365 to on-premises*" -TargetSharingEpr https://mail.contoso.com/EWS/Exchange.asmx -TargetApplicationUri FYDIBOHF25SPDLT.contoso.com

5) Then test again Free/Busy from cloud user to onpremUser@contoso.com

You can use https://testconnectivity.microsoft.com/tests/FreeBusy/input 

6) I also assume that in Cloud Organization (source side) you have a Mail User  for the target user onpremUser@contoso.com with the same External Email Address . It is not mandatory to have a MEU for target user in the source side but we need to make sure that contoso.com is the SMTP domain which Scheduling Assistant would resolve to. Based on this SMTP resolution, we pick the domain from user@domain and lookup for an organization relationship with the domain listed in DomainNames.