Reputation and "the cloud"
As Reddit recently learned it’s not a great idea to use the Amazon EC2 cloud to host mailservers. There are a number of reasons for this, most of them related to the reputation of mail coming from EC2 servers.
When you’re using machines in the cloud, changing IP addresses is as simple as initializing a new server. Spammers discovered this almost as soon as the EC2 cloud became public. They would set up a mailserver and send spam through that server until it was blocked. Then they’d just start another instance to avoid the block and keep spamming. They had an almost unlimited number of IP addresses to abuse and moving around was easy to do. Amazon did little to stop the spam coming from the cloud so many ISPs and spam filtering companies blocked email from the entire range of IP addresses allocated to the EC2 cloud.
Blocking large swathes of network space that are consistent sources of abuse is well accepted as a method of dealing with spam. Yes, this form of blocking has inconvenienced legitimate companies who aren’t actually doing anything wrong. But when a service provider doesn’t take sufficient action to stop customers from spamming through their networks, then ISPs will implement countermeasures.