Background
In February of 2006, AOL instituted a "pay to send" method for legitimate bulk email to bypass the usual AOL spam filtering (which filters out lots of legitimate email as it is). The system, CertifiedEmail, requires the sender to pay a fee of 1/4 of a cent per message, which can amount to thousands of dollars for larger lists. The thinking is that after this is instituted, rather than fixing their broken spam filtering, AOL will just tell people to pay to send their email.
The Opposition
Quite a bit of opposition has arisen as a result of this. An organization called Dear AOL has posted an open letter about this signed by Craigslist founder Craig Newmark, the Association of Online Cancer Resources, the U.S. Humane Society, Oxfam America, MoveOn.org Civic Action, Gun Owners of America, the Democratic National Committee, RightMarch.com, the AFL-CIO, Free Press, the Electronic Frontier Foundation and thousands of others. The reason being that many of the organizations are non-profit or provide free services and simply can't afford to pay these fees.
Solution 1: Pass Along The Fee
The solution I am proposing is to simply pass this fee on to AOL members. After all, the mailers will have to pay to contact these subscribers (and ONLY these AOL subscribers) and these AOL subscribers want to receive this email. So, when an AOL user wants to signup for your email newsletter, charge them $1.00 to subscribe. Even with the unnecessarily high cost of credit card fees, this will still leave you enough to pay the fees for this subscriber for a few years and, when combined, some money to offset the additional work necessary to have a seperate mailing list just for AOL subscribers. When charging the fee, be sure to refer to it as the "AOL Email Tax" and have an explanation that AOL itself has decided to start taxing email and that if the subscriber has a problem with it, they should contact AOL. You may also wish to mention that if they use an alternate email address from a more responsible email provider, they can avoid this fee entirely.
Solution 2: Denial and Alternatives
Since solution 1 can be complicated, an alternate is to simply deny AOL users the ability to subscribe to your mailings. There's a good chance they won't actually be receiving the email they asked for, so you're saving yourself and them some headaches by being upfront about it all. Don't let users with aol.com address subscribe. When they attempt to, forward them to a page with an explanation of being unable to send them free newsletters due to the "AOL Email Tax" (be sure to use this term). Mention that this is a fee instituted by AOL itself and that they can subscribe if they use a non-AOL email address. Helpfully suggest some free email providers like AOL's competitors.
Solution 3: Warning Only
Really a modification of Solution 2, you simply provide a warning message to the subscriber signing up with an aol.com email address that there's a good chance they won't receive the email they are asking for due to the AOL Email Tax. Suggest alternative email providers. But let them subscribe with an aol.com email address after they've read the warning.
Email Service Providers
Email service providers can implement both solutions 1 and 2 for their clients, giving them the choice when setting up mailing lists. Solution 1 can be a bit more complicated (managing alternate lists, processing credit cards where no fee was previously necessary) so starting with solution 2/3 is quite a bit easier (and more immediate). Getting feedback from your clients on what they would like is recommended.