Part of making good backups is knowing that the backup can't change. The only solution now is to add paths to go back and modify those backups to remove customer data when asked too.
That is my plight anyways.
Post hosting providers, or anybody really don't create new volumes for each customer. They would simply have a directory per client. Onces you start needing to know more about the file system then you sort of waste all the benefits block based backups provide.
By block based I mean volume based, were we simply copy the allocated blocks of the file system that changed between each backup.
I guess the real issue is who will be responsible ensuring backups are stored in a way that different clients are isolated.
As somebody who makes backup software I know the burden will at some point be on my plate.
That being said, if people stored data differently, and did actually have a key per customer then the backup software won't matter, because like the parent and you said, just delete the key. But nothing really works like that today, and it will require a massive amount of software to be rewritten to handle this sort of stuff. So until then either you can't backup your data, or you make the backup provider figure it out.