Well any sort of bulk mail is going to result in some amount of complaints, no matter how strict the signup requirements. (some) AOL members have a habit of marking anything and everything they don't feel like getting as spam. I see this with discussion lists as well, sometimes. You also have cases where people are sharing an account and don't realize that someone signed up. Also, there are still some "grandfathered" lists from before the new policy took effect (although we've been requiring confirmation for AOL subscribers for quite some time).
I'm not sure what was happening in this particular situation - we noticed that some of AOL's inbound mail servers seemed to be blocking us while others weren't. When I spoke to someone on the phone over there, they claimed that they didn't see any existing blocks on that machine.
I have filled out a whitelist request form for certain bulk mail machines on our side (particularly the ones sending announcement / discussion lists, and those sending the confirmation messages themselves) - hopefully this should help.
I've generally found AOL pretty responsive - they have a hard job to do, and a whole lot of users. And, unlike other ISPs, they do a pretty good of documenting their policies. The sad truth is that given the current state of the spam problem (with probably 40-60%+ of mail at many sites being spam), blocked and filtered mail are probably going to become more of a problem rather than less.