I actually trust tarsnap more than setting up a host and having to maintain it:
If I do fork out for a service, I would probably rather go with the kind of company that has as their tagline: "Online backups for the truly paranoid", like them.
Pricing's not a killer either.
More than anything else, cpercival earned my trust simply by being honest. There are precious few companies I could say this about.