that's an interesting question, i've given a little thought to this multi tenant saas stuff...
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.