not sure if the right way forward is some sort of innovation in operating system and software design where people write and run apps that feel like single tenant apps attached to dedicated per tenant datastores where os and framework magic handle per tenant encryption and segmentation (tenant id as an os level concept)
or... if it makes more sense to encrypt at the record level with keys that only the customers hold using (assuming it's up to the task) homomorphic encryption for things like searches and other backend functions.
either way, for now, soft deleting and following up with an automatic daily hard delete of things soft deleted more than x days ago is a totally reasonable approach.
ops scripts should require typing "yes i know what i'm doing" if someone attempts to hard delete things that have not yet been soft deleted.
if it forces additional fail safes or backups to be able to do so safely, then that's probably a good thing to have anyway, no?
They may be scared. But are they scared enough to reload every single backup they have, purge the desired records, and resave each and every single backup they have? And not also worry they will corrupt/break the backups in the process.
GDPR compliance is a mess of contradictions and unreasonable asks which all seem to amount to "depends on who you ask."
Perhaps an effective measure would be to create a key that encrypts a customer's data, and give them a copy of the key, and let them know that after a certain point your copy of the key will be deleted, and if they want a restore past that point they'll need to provide the key.