This is why I never have a DELETE call anywhere in my app or admin code. I always mark as deleted (there are performance improvements in this for some databases as well)
I've worked at several places where the strategy is 'never delete, just mark as deleted'. Your database tends to grow pretty fast, but you never have to defragment your index or tablespace.
I usually setup purge tasks (copy to same table in another db) every week or fortnight in low-traffic periods