I love Tarsnap, but S3 storage costs aren't exactly brilliant. Figuring out exactly how you wish to store keys can also be another thought, upfront (albeit one that arises from the increased security that you get 'for free').
Alternately, CrashPlan and other consumer-style services have a bad habit of using very slow, heavy, world-slowing systemwide file update scanning. :/
Having said this, a discussion of the merits and flaws of Tarsnap and similar backup services is something I'm fairly certain I've seen lengthy discussions of on similar HN posts.
