Amazon (or any hosting provider) receives a large amount of IPs from the various Regional Internet Registries that exist around the world. For example, here's a list of IP ranges they had as of Februray 2010:
US East (Northern Virginia):
220.127.116.11/20 (18.104.22.168 - 22.214.171.124)
126.96.36.199/19 (188.8.131.52 - 184.108.40.206)
220.127.116.11/18 (18.104.22.168 - 22.214.171.124)
126.96.36.199/17 (188.8.131.52 - 184.108.40.206)
220.127.116.11/16 (18.104.22.168 - 22.214.171.124)
126.96.36.199/18 (188.8.131.52 - 184.108.40.206)
220.127.116.11/16 (18.104.22.168 – 22.214.171.124) NEW
US West (Northern California):
126.96.36.199/18 (188.8.131.52 - 184.108.40.206)
220.127.116.11/18 (18.104.22.168 – 22.214.171.124) NEW
126.96.36.199/17 (188.8.131.52 - 184.108.40.206)
They assign those IP addresses to their virtual instances just like any hosting provider would a physical instance. There is no functional difference worth noting between Amazon and another host; between physical and virtual hosts. Disregard the virtual nature of an EC2 instance for this topic.
Administrators of firewalls then become aware of the IP ranges that Amazon assigns to its EC2 instances and choose to configure their firewalls to block some or any traffic originating from those IP ranges.
It's basic TCP/IP at play.
- A provider receives a block of IPs.
- The provider assigns the IPs to their servers.
- Administrators block IPs and/or ranges based on known bad behavior.
To address one of your specific quotes:
Therefore, even if you never sent spam yourself, emails you send from
an Amazon instance will be flagged as spam because you are sharing
resources with people who do spam.
The above is true for shared hosting, certainly. However, to clarify, it's also true if you get a dedicated IP that you are not sharing but was abused in the past. Top notch hosting providers will hold IP addresses that were assigned to misbehaving customers and take pains to cleanse them from various IP blacklists (most likely RBLs that catalog abusive email systems, but it could also be on other lists such as those that catalog IPs known to perform uninvited vulnerability scans) before handing them back out to a new customer. However, I fear that such service is the exception and not the rule because there are many stories about customers receiving an IP address that is blacklisted all over the internet and the host not doing much about it.
These IP issues are not just relegated to the shared and dedicated hosting realm. Some administrators / ISPs also block incoming traffic over spammy ports (like SMTP port 25) from known blocks of dynamically assigned public IP addresses. Anyone with a home-grade ISP account will likely be given a public IP address that is dynamically assigned and is subject to change at any moment. Since most email that is sent out directly from a home-grade ISP account and not through a proper authenticated relay are likely from compromised PCs it's not uncommon to simply block spammy traffic from the ranges that are known to be residential class dynamic IPs. Also, most ISPs have a EULA that demands no services be hosted on the connection which makes it easier for the ISP to justify blocking all traffic over those ports from leaving their network (also, the ISPs want to upsell you to business class [read: more expensive] connections that have static IP addresses and don't limit the network services that you can run).
For example, a large range of North American IP addresses owned by Comcast is 220.127.116.11 - 18.104.22.168. Perhaps not all of them are dynamically assigned; it would take some sleuthing to find out what subnets within that range are used for static IP / business accounts and which are used for dynamic residential accounts. However, I guarantee that many blacklists, specifically for email servers, will block email communication that comes directly from one of the IP addresses that are in a dynamic range in that Comcast block.
And that is IP range blacklisting in a nutshell. I'll print it out and autograph a copy if you want.