My only recommendation would be, no matter which strategy you go with, cover it with tests to make sure the right information stays and the right information gets physically (or marked) deleted, and that data marked for deletion is invisible to the UI except via admin access.

But, indeed, proper deletion is surprisingly difficult, especially when you consider cascades on a complex table containing many defined foreign-key relationships.