They could do client side encryption.
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.)