Depends on the problem domain, but flagging the records when user deletes them, and notifying the user that the action is reversible for x days, and allowing th

Depends on the problem domain, but flagging the records when user deletes them, and notifying the user that the action is reversible for x days, and allowing them to delete the record permanently if they want is a sensible approach.