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.]