I have been trouble shooting an interesting issue with a client where If an External User tries to make an audio call to an internal user, the call would not be established due to network issues.
So the first thing that comes in mind are FW ports.Normally you need to double check the TCP/UDP 50,000-59,999 Range as well as the UDP 3478. Well after looking into it the ports were open and Edge was listening on them too.
Now the issue was only with the media, the signaling was fine, So when the External User calls the internal one, the called would get a notification, but when he accepts the call it disconnects.
The General idea of connection is that during the SIP negotiation and Especially the SESSION IN PROGRESS part in the SIPSTACK log, both clients would be offered the possible means of communications in the VIA field, So if you look closely You find the means to be BOTH Clients directly to each other or through an assigned ports on the edge.
Now running a SIPSTACK log on the Front End is saw the following error
ms-client-diagnostics: 23; reason=”Call failed to establish due to a media connectivity failure when one endpoint is internal and the other is remote”;CallerMediaDebug=”audio:ICEWarn=0x80012b,
After checking all ports in all directions it was still not working. So I ran a trace on the Internal Interface of the Edge and saw the internal client connecting successfully to the Assigned Port that I got from Monitoring the SIPSTACK.
What was interesting is the External Interface. When I ran the trace on the External Interface I would see the Edge Denying the connection to the client on the specified port.
Now the Edge would behave this way if the client was not authenticating to it properly, So ahead to the UCCP Logs on the client side I went 
which are located under %Username%\Tracing , But how would the client know where to authenticate ?
Easy when the client signs in, it receives the configuration. and we are specifically looking for the MRAS that we have configured and can be found in Lync Control Panel –> Topology –> Edge Server –> EdgeServer
Now you would ask me, how did the client know how to get there, Remember the SESSION IN PROGRESS Negotiation ?
Looking at the logs I searched for the FQDN I got from the External MRAS FQDN in the previous screen
Bingo, here is the issue. The client doesn’t know where is the AV.domain.com record. SO It means that the DNS record AV.domain.com is missing from Either their local DNS or the external one.
It was actually missing on both, So after creating this record both internally and externally to point to the NATed public IP address of the AV Edge. All Started working perfectly fine.
So in a nutshell,
If you are facing an issue with AV Not working externally check the following
1- PORTS (This is normally the issue)
2- DNS Records
3- Certificates and trusts
Hope this helps
Hany George's Blog - The Old one 
Thanks. I have fixed similar issues before, but now I am seeing the same issue with external companies, who are not federated with us. Federated and our own users (internal or external) works fine. It is just that external companies who are not federated cannot do voice, video etc.
This is the error we see:
26; reason=”A federated call failed to establish due to a media connectivity failure where one endpoint is internal and the other is remote”; CallerMediaDebug=”audio:ICEWarn=0x80012b,LocalSite=192.168.1.105:18996,LocalMR=y.y.y.y:3478,RemoteSite=10.10.0.31:53303,RemoteMR=216.x.x.x:58366,PortRange=1025:65000,RemoteMRTCPPort=58366,LocalLocation=1,RemoteLocation=2,FederationType=1″
My bet would be firewall ports between those other companies, given that your and federated companies connections are fine, you could run a trace with wireshark on the client pc and see. Sipstack from edge is also helpful
i’ve got a similiar issue with AV and content sharing not working between two internal Lync users both signed in externally over the internet (not federated). Chat works but no media. Media DOES work between external and internal users, just not between two external users. Any ideas?
Thanks
Richie
I would start collecting logs, Client logs and Edge SIPSTACK logs are needed in you situation. But given the fact that MEDIA works but not for EXT-EXT i would say its a local firewall problem on one of the ends side if not both.