The founders Isaac and Jose were in Techstars with me this summer, and I highly recommend SendGrid. They've got an awesome plugin architecture too that's an immense time saver for things like adding and managing unsubscribe links.
This is a very large problem that Amazon needs to spend some time addressing.
I run a fairly large production site on EC2 (14 instances) and when we went into production we quickly found out we were unable to send email from our servers to anyone... just about every email provider has blacklisted EC2's address space.
I literally have to run an "off site" server from Amazon as a mail relay to work around this issue.
Word of warning, EC2 is awesome, but this is an important lesson learned if you are moving to the cloud.
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 . 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.
I wish the issue was explained a bit more in the article. In my opinion if the blocking was due to host-names then it had nothing to do with EC2. If the blocking was due to re-use of IP addresses then maybe it had something to do with EC2 (but the article didn't explicitly claim that). As far as I can tell the effect was due to using a outsider server at all (instead of carrying one into the client's own private data center), which I think has nothing to do with having used EC2.
You're right in that all hosting services suffer this problem to some degree, but it's a particular problem on EC2 since it's so easy to request IP for an instance that does something bad, then release back into the pool for other instances to use, a short time later.
It only costs a few dollars to that on EC2, whereas most other hosting services require at least a month's commitment and higher fee(s) before you can defile one of their IP addresses.
BTW, the reason I posted was to find out what other blacklists might be out there, so if your company is blocking access, I'd appreciate letting me know which service they're using.
You're right about the prior activity for the domain, but both Blue Coat and McAfee complained based on the IP address we're using now (i.e., the EC2 address).
But my purpose in posting this is to ask: what other filtering lists are out there?
Getting ourselves off is easy now, since we are a legitimate site; the hard part is figuring out who else may be blocking us.
I think this speaks more to the low quality of these blacklists than to a problem at Amazon. Did anyone who noticed the offending site contact Amazon to have it removed, or are they simply content to keep adding more blocked IPs as the offender jumps from server to server on EC2?
Seems like this points to a longer term problem with blacklisting by IP address as they continue to become more transient with respect to the hosted service.
When creating mail severs for testing purposes, we too have noticed that many of the IP addresses in the AWS pool are indeed on blaclists or private reputation lists. A smarthost is certainly recommended if you want mail from one of these IP addresses to make it past spam filters. In theory, once you've had the IP address for a while, you should be able to get it delisted and cleared up, but some of these lists and toosl will just block entire subnets that are known to frequently change hands. I think the only real solution would be for Amazon to set aside some IP space and call it premium, and only give it out to validated or longstanding customers, IMHO.
I am the founder of http://critsend.com, we make your email ends up into its appropriate inbox.
We have a special offer for EC2 customers, we have some servers directly at AWS so latency is low and bandwidth is free for them.
We are currently in closed beta but if you subscribe and add say you saw us on Hacker News, we will send you an invite asap. Our first 1,000 emails are free and after that we are pay per use.
