Email Issues With AOL Despite RDNS And No IP Blocks

This is an issue I've been having for a few months now and haven't been able to resolve yet with my data center, AOL support and the company who manages the server for me. My main reason for posting this is for a fresh set of eyes and to see if anyone else has had a similar problem in the past (and how they fixed it)

The issue is this:

I set up a dedicated server to host my web design clients a few months back and no one has been able to send to or receive mail from AOL addresses. I've gone through everything at the postmaster.aol.com site and have ensured that reverse DNS records are in place for all IPs associated with the server, as rDNS is a mandatory requirement for AOL.

Once my support requested was finally elevated to a real AOL support tech, they confirmed that my IP was not being blocked by their servers and are still under the impression that the problem must be on my end somewhere. Because this problem only occurs with AOL (we can send/receive with all other big providers - yahoo, hotmail, gmail, hush, etc), my server management team are fairly certain it must be an issue on AOL's side.

When sending mail from an AOL address, it bounces back with an error like so (real emails replaced with example addresses):

451 <email@exampledomain.com>... exampledomain.com: Name server timeout
Message could not be delivered for 2 hours
Message will be deleted from queue

When sending mail from my server, it bounces back with an error like so:

A message that you sent could not be delivered to one or more of its recipients. This is a permanent error. The following address(es) failed:

exampleaddress@aol.com
retry timeout exceeded

When attempting to manually deliver a message to AOL from the Mail Queue in WHM, I get an error like so:

Message xxx-example-number is not frozen
delivering xxx-example-number
Connecting to emr-d01.mx.aol.com [205.188.159.2]:25 ... failed: Connection timed out (timeout=5m)
LOG: MAIN
emr-d01.mx.aol.com [205.188.159.2] Connection timed out
Connecting to emr-m01.mx.aol.com [64.12.136.169]:25 ... failed: Connection timed out (timeout=5m)
LOG: MAIN
emr-m01.mx.aol.com [64.12.136.169] Connection timed out
LOG: MAIN
== example@postmaster.aol.com R=lookuphost T=remote_smtp defer (110): Connection timed out

When attempting a manual telnet test from my server to AOL's mail server at , it also times out with the following:

Trying 64.12.137.184 (connection timed out)
Trying 205.188.156.248 (connection timed out)
Trying 205.188.159.57 (connection timed out)

telnet: Unable to connect to remote host: Connection timed out

The AOL support tech explained that if my server IP were being blocked, it would return messages with a block error code instead of timing out. They suggested my firewall was blocking AOL's server....but both my data center and server management company said that isn't the case.

Because I can't duplicate this problem with anyone but AOL accounts, I don't know what else to troubleshoot or look for. I know AOL is notorious for blocking IPs and most email related problems are usually for lack of rDNS, but neither of those issues are the problem in this situation...so I don't know what else to try. My server management company (PSM) and AOL (once they finally elevated me to a real tech support person), have been very patient and helpful....but we still haven't been able to identify the problem and I feel incompetent for not being able to contribute on my own. I've researched for weeks and certainly understand more than I did, but still far less than they do.

AOL did direct me to a Windows Server troubleshooter relating to UDP packet size limitations with some firewalls that could cause MX query timeouts with AOL, Earthlink and Quest...but because I'm on an Apache server...I didn't know if that could be related at all to my issues (not to mention that I didn't even know what any of that meant until I went and looked up what a UDP packet actually was. I'm still not entirely sure I understand it). Even so, I did send the information to Platinum Server Management a short while ago, but haven't heard back yet.

Anyways.... in the meantime, I thought I'd check here in case anyone else had the same issue or saw something obvious we might not be considering.

My server details are as follows. I included my data center and management company details to illustrate that people far more qualified and intelligent than myself have performed the most common and obvious troubleshooters so far:

Pentium IV 2.8GHz /1GB DDRAM /120GB EIDE HDD
OS: CentOS 4.3
cPanel/WHM
Main Server IP: 66.79.163.138
Example Domain on the server: vedadesigns.net

Data Center: Dediwebhost.com (awesome service & fast support)
Initial Server Setup & Management: Platinum Server Management (I just can't say enough good things about these people)