The blacklisting you experienced, could have happened with any other host. I've seen this happen with dedicated hosting companies, where a server was previously

The blacklisting you experienced, could have happened with any other host. I've seen this happen with dedicated hosting companies, where a server was previously used by spammers and the ips allocated to a new client. When they try to send mail, guess what they're on all the major rbls. As far as sending mail out from the EC2 environment, that's an on going problem. Take a look at this http://www.spamhaus.org/sbl/sbl.lasso?query=SBL79954 http://www.spamhaus.org/sbl/sbl.lasso?query=SBL79954 . I think AWS users would be willing to pay for clean ips that are rate limited. Maybe an EC2 SMTP Service. Your block is using a browser bl and I don't know how those are shared by http filters.