That's certainly a valid point, but it still doesn't solve the problem of having to remember to delete something in the event of data loss.

As far as I can tell to comply with a deletion request with absolute certainty requires infallible storage (which would remove the need for backups) or modifying backups (which contradicts the concept of a backup). Maybe you can claim 'force majeure' at some point, but perfect compliance seems impossible.