I had similar problem a while ago, in my case with AOL and Yahoo. The background was, that because of a failing mail server we needed a new one quickly.
This new mailserver became available before the appropriate DNS entries, especially the reverse DNS entry, were propagated. Obviously this led to the mail server being blocked by those providers. So checking the reverse DNS entry today does not guarantee an error in the past didn't cause this.
Besides what I learned on this occasion is, that all of those providers don't seem to reevaluate banned mail servers. Once you are on the black list, you stay there for quite a long time. As our first mail server could luckily be restored, we could check from time to time what AOL and Yahoo would do with the new one (second MX). Mail were blocked for two months, despite the mail server being configured with DKIM etc. until we formally applied to be removed from the blacklist - which took another 2 days.
With AOL you should use the appropriate from for applying to be removed from their blacklist; suppose Hotmail has something similar.