Re: Backups aren't the problem
"Erm, yeah, but I've deleted everything about Joe Bloggs of Wankstain, Essex, including his request to be deleted."
Two points. If you have some central record ID and that gets used as a foreign key in every other table affected then retain that foreign key. Otherwise retain the request. It will be needed to re-delete on restore. Without it you can't do as he asked so if you deleted it it you were doing it wrong.