Even a one-year-old start up could have literally thousands of database dumps in different places if they followed best practice of triple redundant daily dumps.
* Have a clear data retention policy and make sure that all backups have an expiration date.
* Secure your backups with strong encryption to protect user data in the event of a leak.
* Explain it to the user when the account is deleted when the deletion will filter through your backups.
* Guarantee that if a restore is needed, their data will be immediately deleted from the restored system.
I'd suggest this is a reasonable safety/compliance balance.
You have to do very little if you're keeping backups for less than month, simply delete from the DB and wait for backups to age out:
https://ico.org.uk/for-organisations/guide-to-the-general-da...
If you are keeping for longer than a month be prepared to justify that.
> This is made even worse if you have multi region backups and cold back ups.
You should be automating this. I assume you're automating the dumps. Automate the deletion. Deleting three encrypted files off S3 every day really isn't particularly hard. I've written stuff to do this a bunch of times.
> Even a one-year-old start up could have literally thousands of database dumps in different places if they followed best practice of triple redundant daily dumps.
If you have backups sprinkled willy-nilly about the place that you may have lost track of then it shows you have a significant lack of care about my data, and so I don't want you to have it at all.
If information is backed up (in a way that it cannot be easily accessible and queried directly from the backup,) and the backups are stored securely, and there is a mechanism/policy (it doesn't have to be a purely technical measure) to replay the deletion in case if the backup is restored, you're going to be fine.