Cannot send mail to AOL, Qwest, Hotmail, Earthlink, etc

Source: Microsoft Support

RAPID PUBLISHING

RAPID PUBLISHING ARTICLES PROVIDE INFORMATION IN RESPONSE TO EMERGING OR UNIQUE TOPICS, AND MAY BE UPDATED AS NEW INFORMATION BECOMES AVAILABLE.

All mailflow to the internet works except to domains such as AOL.com, Qwest.net, Mindspring, Earthlink and Hotmail.

Messages sit in the outbound SMTP queue and eventually time out with a destination unreachable NDR.

Some mail servers (such as AOL) require you to create a valid PTR (or reverse DNS lookup) record that points the sending server's IP address to the local SMTP domain namespace. Sometimes they require it to match to the actual FQDN of their SMTP Virtual Server on Exchange (typically the MX record).

Create a valid PTR or reverse lookup record on your companies external/internet DNS server.

Steps to Repro

A simple telnet to port 25 on one of the AOL MX records shows:

220-rly-ya06.mx.aol.com ESMTP mail_relay_in-ya6.3; Fri, 20 Jan 2006 22:15:42 -05
00
220-America Online (AOL) and its affiliated companies do not
220-     authorize the use of its proprietary computers and computer
220-     networks to accept, transmit, or distribute unsolicited bulk
220-     e-mail sent from the internet.  Effective immediately:  AOL
220-     may no longer accept connections from IP addresses which
220      have no reverse-DNS (PTR record) assigned.

Also see the following regarding EDNS:

828263 DNS query responses do not travel through a firewall in Windows Server 2003
This can also cause this problem.

For additional information on PTR records:

166753 Microsoft DNS Server Reverse Lookup Error Adding Host Record