How am I not already aware of these guys? Pricing looks good.
Of course, you can’t rsync to S3 so I’m handling backups with duplicity and using S3 as the storage target.
Thankfully I’ve not had to perform a complete restore, though I do regular test restores of a part of the backup just to make sure it’s all still working.
Edit: It’s actually $100 (as transfer from S3->Internet adds $0.09/GB)