The issue was that an internal user was not able to send messages to a federated partner but they could receive messages as shown below. User receives error:
When contacting your support team, reference error ID 504 (source ID 239).
Find out what the external users SIP address is so you can verify if you can telnet to that address on port 5061 from the Edge server.
(Currently this may fail)
FIX: Verify the Federated domain’s certificate is installed on every Lync Edge Server (if you have more than one). Once it is the issue should be resolved.
Open up Certificates within MMC and browse to Trusted Root Certificate Authorities > Certificates.
(In this case, “Corporate Root CA” is the certificate for the Federated Partner) The original issue was caused by this certificate not being installed on every Edge server as is needed to work correctly.
Attempt to telnet to the SIP domain on port 5061 again and it should be successful.
The user(s) are now able to send IM’s to the federated user successfully.