Cannot you point them to the warning and be done with it after a complaint, or is the amount of the complaints and its handling is the issue?

When I say warning, I'm talking about a prompt after attempting to delete that asks if they are sure and clearly states that the action is permanent. This would display on every attempt to delete a record.

Yeah, but why care if they did not see the warning and they actively clicked on it? It is their fault.