I don't feel like leaving the records in-table is that terrible. Maybe even partition on the deleted-at column to keep the performance impact minimal. The benefit of simplicity massively outweighs the rest for me