Have you tried telnetting to that mailserver first: telnet mailserver.brokendomain.com 25 and verifying that it signs on? It may just be really slow and is truly timing out. The only fix for that is to change your timeout settings.
Yes, I tried a telnet and it responds right away. I was able to send a helo and it acknowledged me. It's baffling. I don't know where else to look for this. Thanks for the reply. -- -=/>Thom