Very often when diagnosing mail problems it is helpful to see exactly what SMTP responses are being generated for every step of the transaction. Frequently the root cause can be found by closely inspecting the responses from the HELO and RCPT TO portions of the SMTP conversation. Now Mailive! can help out.
Recently Mailive! began recording outgoing SMTP sessions for all test messages the system sends. Now they can be viewed through the interface as shown here.
If there is a problem connecting to the mail server being tested there will be no output to capture. If any portion of the SMTP transcript is able to initiate there should be some evidence available to inspect.
Hopefully this will help diagnose some of the more transient and hard to find problems.