Practically every system I've built at scale uses soft-deletes. A flag is put into the database and records that are deleted are excluded via that flag.

Note that I'm not playing with people's identities, but even then, you have to ask whether they were paying to delete the availability of their user data or the actual database records (somewhere in the contract?).

I think they should be clear about whether the information is still stored, true. But I also do sympathize with AM in this situation. I'm sure many of us have had the experience of going out of our way to secure someone's system for them, and then being asked years later if we can help them when they've locked themselves out. I'd be willing to bet there were more than a few people who paid to have their accounts deleted and came back at a future date and wanted to pick up where they left off.

I've dealt with PII, and soft-deletes are explicitly disallowed. But I work in an industry where "delete" is something to be very carefully defined.

Their overall security procedures may have been good, but at the very least the fact that they charged money for permanent deletion of data and then didn't actually permanently delete data ought to qualify. People who just signed up may not have a case, but anyone who "deleted" their account does.