daaamn 20PB (~20,000,000 GB ) ... AWS Dynamo charges $0.25usd per gigabyte per month of storage. If they are using AWS, they would be paying $0.25 X 20,000,000 (GB) => $5,000,000 usd per month (only for storage). If they're using AWS, I'm pretty sure they got some kind of enterprise deal.
Not entirely sure either. As far as I know, AWS assigns one public IP from a pool of reserved IP's to each EC2 instance they provide. I suspect that the companies that provide this kind of service, take advantage of this feature and create a couple of thousands of micro EC2 instances, and somehow, relay a request from X source to any of these available instances. If any of them were to report that it cannot access certain services anymore (let's say, it gets blocked by Google), the EC2 instance would get killed by a monitor process and create a new one with a new IP.
That's just a guess though, I'm far from being a network expert.