Demystifying Hybrid Free/Busy: Finding errors and troubleshooting

1.  Do I these URLs need to be accessible on all Exchange Servers or just Hybrid Server is enough ?

>> ALL the Exchange 2010 MBX & CAS or 2013 MBX (backend) or 2016 would need outbound Internet access to all these:

• Office 365 URLs and IP address ranges – Exchange Online
• Office 365 URLs and IP address ranges – Common
• Additional endpoints

Reference: https://docs.microsoft.com/en-us/previous-versions/office/exchange-server-2010/dd638083(v=exchg.141)?redirectedfrom=MSDN#firewall-considerations-for-federated-delegation 

2. The other thing you advised is that if I disable On Premise IOC and populate Organization Relationship with https://outlook.office365.com/ews/exchange.asmx Free / Busy look up will not use Autodiscover but it will use EWS and that may resolve my issue ?

>>Yes, correct, you can try to bypass AutoD query and see if it works by going directly to EWS but this can be any on-premises Exchange Server in your organization, so internet access is needed from each.