[lmikle]

Ну, сделай логическое удаление, а не физическое.
Добавь в таблицу дополнительное поле-флаг и просто выставляй его когда запись удаляется. А во всех запросах пользователя просто отфильтровывай такие записи.