I managed to resolve this issue. The problem was my internal mail gateway that receives external all inbound emails is using non-internet routable domain that does not resolve in the internet.
After creating a new hybrid SSL certificate that i added the FQDN of that gateway, office 365 users were able to send to on-premises users without issues.