Catch-22
I am also experiencing AOl email rejection. First they said is was a reverse DNS issue (we were getting a similar message in their bounced emails). We have now fixed that (if you do an nslookup on the base IP of the server, it returns the domain name that a ping of smtp.domain.com belongs to. If you ping smtp.domain.com, it returns the IP address of above). I
Email then worked for a day before getting rejected once again. This time with a new message in the bounced emails stating it is an open-relay or has been blacklisted for spamming. When we talked to them the first time, they said we are not blacklisted, and their own online tool says we are not an open-relay. It's a never ending battle with them. We've had our ticket open for over a week and still no resolution.