Yes, after working with MS for nearly 1 month and no help to find what was causing the blockage, we finally reverted back the Mail Flow to On-Prem Servers and it started working.
When I say maiflow we were doing only few changes with respect to DNS both at the External DNS and Internal
So, not sure what was going on at the Network Level, which was causing the blockage as we had many times asked our Network to open and give access for the Office from the DR side as suggested by Microsoft and they said everything is open.
Anyway we had only few Resource Rooms which were connected to some Third Party Device for booking which had restrictions, so we could not move them to O365. Now ,we will try to move them to O365 and once moved we should not face these kind of issues.
Thanks Dan for suggestions as I was left without any help and as the issue was complicated and getting escalated we had to stop further troubleshooting and bring back the flow to Primary servers.