A better way to do this sort of thing is not an actual "delete", but a "cryptographic delete". The data should be encrypted, and you just delete the key. The data is then unrecoverable everywhere, including backups. Of course you probably don't want to just nuke the key, but disable it for some period of time, and then nuke it.
i don't see how that really changes anything - your keys should be backed up just as much as, if not more than your data. and any process for deleting the encryption keys should allow for restoring from backups for some period of time just the same as your process for deleting data should allow restoring from backups for some period of time. either way, permanently rendering data as unrecoverable takes time.
As an example, if you are using Amazon's KMS for key management and you destroy a key it gives you 7 days to undo before permanently destroying the key. Or you can disable they key and destroy it later as your retention policy permits. Surely they have some kind of key backup, but KMS users have no access to those backups.
