A very close approximation to patio11's vision of what tarsnap should be already exists: http://www.rsync.net. I use them with duplicity instead of tarsnap for exactly the reasons patio11 went in to.
All the same benefits as tarsnap: de-dup, guaranteed privacy, OSS, headed by a bona fide geek (http://blog.kozubik.com/), fair pricing. Plus: multi user sub accounts, 7 days of free server side snapshots of your entire backup space and geo redundancy.
Plus business benefits: SAS 70 / PCI / SOX / HIPAA compliant, a company that's been going for over a decade and isn't reliant on one person or supplier etc.