I'm currently using s3sync, a ruby script that gives rsync like functionality with Amazon's S3 service, to store some of my more irreplaceable data. However it looks like maintenance of the program has become a bit spotty. The latest updated version can be found on Github.
I haven't converted yet, but it looks like Tarsnap might be a solid replacement. I'm going to work on rewritting my scripts and I'll document the process of backing up to this service.