安徳ともうします。

一つの方法ですが、、、

・レコードを物理的に削除するのでは無く、フラグを立てるなどで論理的に削除
・削除IDを管理テーブルなどで管理
・追加時には、フラグを戻してデータを書きかえる

この方式ではいかがでしょうか？
どうしても物理削除が必要な仕様ならゴメンナサイ