Running into this issue, where the first call made from a Lync Client to a federated partner like MSFT fails. The call shows connecting, and then fails citing network issues. In the logs, I can see the error: A federated call failed to establish due to a media connectivity failure where both endpoints are internal". I can see the Local and Remote SITE and MR IP address just fine.
Also on my edge server the persistent route is already configured with a subnet mask of 255.255.0.0 and a default gateway as well.
The Edge Server has the latest CU installed, and we are using three different IPs for A/V, Web and SIP.
I saw blogs online, where everyone pointed to the persistent route being missing, Which is not in my case. Am i missing on something here. I really doubt it to be route issue, because the very next call goes through and the calls after that too. If i wait for say about thirty minutes. the first call fails again with the same error code as mentioned above.. and the rest of the calls work just fine.