Receiving dreaded "The connection was dropped by the remote host." error in Exchange 2003.

This has been an error tossed around a 100 times over, but here we go again, since the other KB's simply are not helping.

On currently a single external domain, (not gmail, yahoo, or the others, but a private business), we are receiving the message in the queue "The connection was dropped by the remote host." After 24 hours, the message dies and the NDR that it could not be sent in a timely fashion is sent out, pattern repeats.

The standard ideas are either fixed or not working: Symantec Antivirus is not running; I have turned the Symantec Mail Security on and off and that does not help; our rDNS is correctly matching our email server ("mail.abc.com"); the FQDN of mail.abc.com is listed in the Advanced Delivery section of teh SMTP Virtual Server Properties. Oh, and we have the latest hotfixes for Windows Server 2k3 AND Exchange Std. 2k3.

Now what is interesting is according to the other company, they can receive email fine from everyone else but us, and they can send email TO us. We simply cannot reply back. Now one thing I did find out when I attempted to telnet is that the domain names ARE different for them...email is jdoe@dog.com, but MX record is mail.CAT.com. I have to wonder if that is causing an issue, but I am simply stumped of what I can do from here.

Help is needed!