As another point of redundancy:
This guy advertises himself as "online backups for the truly paranoid".
http://www.tarsnap.com/The guy is kind of a math and crypto whiz. He used to be Security Officer of FreeBSD; don't know whether that's the case still. He's cperciva at Hacker News. His personal website:
http://www.daemonology.netGiven his pricing policy:
Tarsnap has no fixed or minimum monthly fees!
Tarsnap is billed only based on actual usage — if you only store a small amount of data, a $5 payment might last you for years.
I bet he could be convinced to take bitcoins.
[Disclaimer: I don't know the man nor am associated with him in any way. I have never used his service and I can't vouch for it first hand. It just seems an obvious fit for this thread.]