You trust the end users to back up their private keys?
tarsnap is nerdish, secure and reasonably priced for what it provides IIRC. Haven't used it though but expect someone would have yelled out here if it was bad. (In fact the only one I've seen bashing it was patio11, -because it was too cheap and too nerdish.)