Cloud-based backup solutions that I have tried or looked at so far (such as tarsnap, dropbox, crashplan and some others), would allow an attacher to delete all backups (including "previous versions") in case of a host compromise, which is a scary prospect.
What cloud-based backup solutions are available that are actually guaranteed have your back in case of host compromise?
