We just have a history table (for each table) where all deleted and past versions of record are stored. Seems to solve all the issues. The history table is NOT part of the application, but is there for audit and diagnostics etc.