Issue Resolved. I had to disable OAuth in Office 365 by running the following PowerShell in Exchange Online:
Get-IntraOrganizationConnector| Set-IntraOrganizationConnector -Enabled $false
Confirmed that TargetApplicationUri, TargetSharingEpr, TargetAutodiscoverEpr are configured in Exchange Online.
Get-OrganizationRelationship | Set-OrganizationRelationship -TargetSharingEpr https://mail.abc.com/ews/exchange.asmx -TargetAutodiscoverEpr https://autodiscover.abc.com/autodiscover/autodiscover.svc/WSSecurity
Enabled the Federation Trust in Exchange On-premises as it was not enabled by hybrid wizard (Exchange Admin center > Organization)
Added the abc.com in Exchange On-premises "Organization Sharing".
wait 5 mins and Free Busy started working both ways.
OAuth sucks..