They probably would use replication to a different region/zone and then they implement their own snapshot/backup mechanism on those replica machines so that they can use them to re-create instances when they lose them. Also PostgreSQL ships logs that you can store in S3 and bring up an instance from another area starting from a known backup point.
EBS is a pretty bad product regarding reliability and consistency of performance unfortunately, it's better to design your system without it.
Re-building by reading logs out from S3 can be very slow. It should be seen as a last ditch effort. Not really a hot swap, or fail over solution (depending on data size obviously).
If you can't use any persistent storage, then these machines become pure processing nodes. Which in this case, I feel like it would be better to not design your system with EC2 at all. :-(
To me having EBS made EC2 a very powerful solution compared with their competitors. Not having durable and consistent EBS otherwise makes no point in differentiation and serves purely as non-functional fluff we end up paying extra for.
If I were them, I'd look at an approach that was based on either SimpleDB or S3. I've been working on a couple of prototypes of systems similar to theirs for my own stuff at work, and I've been toying with a system that uses S3 to store what I'm calling "absolute fallback" sources of data for conversations (basically, JSON documents) and SimpleDB as a front-line store.
My general take on this issue is that if you're running your app on EC2 and your persistence medium is something that's also on EC2, you really have no ideal high availability scenario. Of course, even in my case, if SimpleDB and S3 go down, I'm still in trouble, but at least I have the option of throwing Akamai in front of it.
EBS is a pretty bad product regarding reliability and consistency of performance unfortunately, it's better to design your system without it.