I was adding a federation between a external party and a customer i work with that is running a Lync 2013 envirronment.
After adding the federation i ran the Test-CsFederation command in powershell to see if it was working before i asked the users to test. The first test took some time before returning a 504 time out error. Every test after that instantly gave a 504 timeout error.

I had previously successfully added several federation partners to the front end server. I also tested to federate against this external party from another customers front end server. Same result. Timeouts ussually happen if for example latency is very high, but there were no problem with the servers connection, also since it was the same result from two differrent customers. This is were its the OCSLogger´s time to shine. The tool is part of the Microsoft Lync Server 2013 Debugging Tools suite.

I ran it on the edge server, then replicated the problem. After the log file was collected i pressed Analyze to open it in Snooper (a tool for reading Lync logs, and also part of the debugging suite). I could see that  there was an error. The external parties edge server was denying access.

After googling around a little bit, it could look like the external parties edge server is not giving us access because either we dont have their certificate or they need my customers certificate for identification. After adding the external parties edge server certificate to my customers edge server root certificate store, i did the test again. Same result. To not interrupt the customers  service to much i scheduled a reboot of the edge server at friday night. After returning to work on monday morning i did the test once more. Still 504 timeout.
Next was to have the external party to add my customers certificate on their Edge server.
After running the test now, the federation test went successfull!

Once again logging/Snooper have helped me. Thanks Microsoft for making a good way to run diagnostics to find errors.