This is a brand new Lync 2013 build. Inbound federation including IM, presence (of the local user) and video works if the external party starts the chat However, if the IM conversation is started by a local user it fails. I've ran Wireshark on the external interface of the Edge server and when trying to start an IM conversation over federation from the local user no traffic leaves Edge server destined for the Edge server of the federated company. Below is a cs-testfederatedpartner against microsoft.com.

**********************************************************************

PS C:\> Test-CsFederatedPartner -TargetFqdn hq-les01.contoso.com
Domain microsoft.com
Test-CsFederatedPartner : A 504 (Server time-out) response was received from
the network and the operation failed. See the exception details for more
information.
At line:1 char:1
+ Test-CsFederatedPartner -TargetFqdn hq-les01.contoso.com
-Domain m ...
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~
    + CategoryInfo          : OperationStopped: (:) [Test-CsFederatedPartner],
    FailureResponseException
    + FullyQualifiedErrorId : WorkflowNotCompleted,Microsoft.Rtc.Management.Sy
   ntheticTransactions.TestFederatedPartnerCmdlet

**********************************************************************

When the federated partner starts the chat IM, voice and video works fine both ways so certificates are valid on the Edge. No errors are logged on the Front End, Edge or the federated partner's Edge (I've looked myself) when the communication fails when the internal user starts a federated IM conversation. Things I've tried.

• Removing the Edge associated with the Front End pool and re-creating it
• Restarting the Edge server
• Disabling federation at the site level and recreating
• Everything on this guide - http://lyncdude.com/2014/05/29/complete-guide-troubleshooting-lync-federation/
• Everything is patched to the latest CU for Lync 2013

I ran some Lync logging for the IMAndPresence and found the following logged.

**********************************************************************

Trace-Correlation-Id: 1671422159
Instance-Id: 1B72
Direction: incoming;source="internal edge";destination="external edge"
Peer: HQ-LFE01.contoso.com:55792
Message-Type: request
Start-Line: ACK sip:peter.pendlebury@silverbug.com SIP/2.0
From: "Lync Test 1"<sip:lynctest1@contoso.com>;tag=6d199fac3a;epid=6bb25f5a5e
To: <sip:peter.pendlebury@silverbug.com>;tag=75C89881F90D1E14A4FEADE9767E4AF2
Call-ID:  713feda84f2d4e2f879c94dd9c0e13df
CSeq: 1 ACK
Via:  SIP/2.0/TLS 10.7.2.71:55792;branch=z9hG4bKAA60A485.0C54DC984FC119FF;branched=FALSE
Max-Forwards:  70
Content-Length:  0
ms-diagnostics-public:  5012;reason="ACK is being generated on receipt of a failure final response for an INVITE forked by application";AppUri="http%3A%2F%2Fwww.microsoft.com%2FLCS%2FUdcAgent"

Severity: warning
Text: The request URI domain is internally supported and cannot be routed to a federated partner
Result-Code: 0xc3e93d75 SIPPROXY_E_EPROUTING_MSG_INTERNALDOMAIN_NOTALLOWED
SIP-Start-Line: ACK sip:peter.pendlebury@silverbug.com SIP/2.0
SIP-Call-ID: 713feda84f2d4e2f879c94dd9c0e13df
SIP-CSeq: 1 ACK
Source: HQ-LFE01.contoso.com:55792
Data: domain="contoso.com"
$$end_record

Direction: incoming;source="internal edge";destination="external edge"
Peer: HQ-LFE01.contoso.com:5061
Message-Type: response
Start-Line: SIP/2.0 504 Server time-out
From: "Lync Test 1"<sip:lynctest1@contoso.com>;tag=6d199fac3a;epid=6bb25f5a5e
To: <sip:peter.pendlebury@silverbug.com>;tag=75C89881F90D1E14A4FEADE9767E4AF2
Call-ID:  713feda84f2d4e2f879c94dd9c0e13df
CSeq: 1 INVITE
Via:  SIP/2.0/TLS 10.7.2.72:49355;branch=z9hG4bK96A668F3.C7179E0556AC79FD;branched=FALSE;ms-received-port=49355;ms-received-cid=188F00
Via:  SIP/2.0/TLS 192.168.30.126:65461;received=217.138.8.99;ms-received-port=50590;ms-received-cid=3A00
Content-Length:  0
ms-diagnostics:  1003;reason="User does not exist";destination="peter.pendlebury@silverbug.com";source="lync-edge.contoso.com"

**********************************************************************

Needless to say silverbug.com it's not a SIP domain deployed on this new environment. Been tackling this for a while now and never seen this sort of issue before. Any suggestions welcome.

It looks like you Edge configuration is not ok.

Please check:

Edge Gateway is configured on the external NIC

DNS Points to the external DNS

Routing entries for the internal Network are done by route add

Edge Server can resolve the FQDN names from the internal Lync Server by host entries or DNS

The Edge Server FQDN can be resolved by the internal Clients.

Firewall are set correct for the needed ports

Was DNS, can't believe I missed that! ;-)