Internet mail routing problem

We are having issues routing mails to a few internet domains. 99.5% of our mail is routed correctly to the internet. The remaining 0.5% appear to have the following issue:

Routing mail to an internet address that is hosted or 3rd party routed fails. For example, assume you send an email to myfriend@somedomain.com. Per the MX record for somedomain.com, the address is xxx.SomeoneElse.com. So my assumption is mail is forwarded by the registrar to a mail server on somedomain.com or stored by a hosting company on its own mail servers. Our Domino server will constantly poll xxx.SomeoneElse.com to attempt to send the email. Eventually, it gives up and we receive delivery failure reports. However, if I jump to my Hotmail.com account, the mail is delivered successfully and almost instantaneously. I had one of the intended recipients mail me something and the email was routed correctly to my inbox, so the problem is only outbound. According to the IT person that performed this test, they are not currently blocking any IPs nor is their spam filter routing the mail to a junk folder. The mail never leaves our server (it remains in Mail.box).

We ran some TelNet tests and here is what we determined: The connection is dropped/refused when tel netting from within our corporate network. However, tel netting from an open, un-associated DSL line allows us to connect (HELO). We’re pretty sure the receiving SMTP server is refusing our connection but we don’t know why.

Any ideas?

thnx,

Subject: Also, some Mail servers do Reverse DNS Checks to verify the hosting server.

Subject: RE: Also, some Mail servers do Reverse DNS Checks to verify the hosting server.

Thought about that too and I think we fixed it, but can you tell me more? That is, the reverse DNS lookup returns our mail server and domain correctly (per DNSStuff.com). Does the reverse lookup only look at the domain? That is ImFrustrated.com or does it look at the entire result: mail.ImFrustrated.com?

What is the criteria for rejection based on the reverse dns lookup?

Subject: Goto:

http://www.dnsreport.com/and verify your ImFrustrated.com domain. It does extensive Mail checking on your domain.

Subject: Internet mail routing problem

Have they enabled DNS blacklist checking? Is your IP on a DNS blacklist. We had a customer this week who was on a blacklist as a result of the previous user of the IP address some 2 years ago…Worth check.

Subject: RE: Internet mail routing problem

The contact is supposed to check with his hosting/registrar to see if that is the case. Even though the correspndence is business related, I doubt he will go out of his way to look into it though.

We have googled for black lists and have not found ourselves on them, including:

http://www.dnsbl.org/

relays.ordb.org

sbl.spamhaus.org