I've arrived late on the thread.. but hopefully most of it's still fresh in everybodies mind..
What AOL is doing here is following best practises with regards to MTA delivery to ensure the least amount of spam delivered. This issue is covered in various RFC's:
as well as rfc1912.
So AOL is catching up with corporate types, ISP's mailhosts and SMEs accross all sections of the internet community. The general consensus is that loads of spam come from ip addresses that do not have a corresponding DNS entry.
To check the condition of your address space, visit [samspade.org...] and enter in an ip address and press the 'do stuff' button. your return reply will be something along the lines of:
Server Used: [ whois.apnic.net ]
22.214.171.124 = [ you.somedomain.net ]
If you do not have a correctly setup RDNS, the value in the square brackets will be blank.
Setting up an RDNS for your mailserver is trivial for competent administrators; Liane this may not be you; but it certainly "should" describe the company that hosts your website. Unfortunately I must digress and quote you:
"My ISP has found no reason for these bounce backs. My web host is at a loss as to why its happening. I've written to AOL without a response. Who knows ... maybe they never received my message!? LOL!"
This is an obvious indication of their cluelessness. 'Bounce backs' and so forth are logged and information is provided as such:
Oct 17 19:20:12 kt sendmail: i9I0KCf28110: ruleset=check_rcpt, arg1=<email@example.com>, relay=[126.96.36.199], reject=450 4.7.1 <firstname.lastname@example.org>... Relaying temporarily denied. Cannot resolve PTR record for 188.8.131.52
Denying emails from hosts without an RDNS (ptr) record is entirely within reason, As in this example above, there's no way to tell where this email is comming from. I might add that kmarcus' response can confusing.. most implementations of this don't require that the RDNS matches forward, just that you resolve to 'something'... even if it's dialup-121.isp.com ... at least its something! :)
Further to this, just to touch on 'plumsauce' response to SPF... I believe it's the 'Sender ID' framework that you wish to dislike; it's a proposed standard by microsoft and is incumbent on many software patents. Implementation of this scheme by anybody using open source is impossible; and anybody not wishing to pay microsoft just to stop spam that originates from compromised windows systems...
I cannot find an RFC for SPF, only rudimentary documentation on it's use therefore IMHO it is not yet ready for primetime, but it does look to soon be another weapon in our arsenal on spam and spammers.