Maybe tarsnap?

You can do a write only key on the server and backup that way then keep the read and delete key off of that and use that only if you need to restore/check backups.

Depending on how much you are backing up it will probably be less than 2000/mo and it is hosted on s3 so there is quite a bit of reliability there.