Our current system uses soft deletes, and I wish we had done a "deleted" table.
The biggest downside to soft deletes for us is that it ruins the default indexes cause every query has a !IsDeleted where clause added to it.
this works better if you split your whole schema into a physical and logical layer, which is a lot of boilerplate but seems like a pagni as well since physical concerns that shouldn't change logical semantics always eventually creep in. this entails at least a view with instead-of-delete triggers and making all indexes be filtered indexes for all tables so it's a lot of boilerplate.
Wouldn’t partition indexes solve this?
Yes, we use filtered indexes to mitigate it. It's a lot of additional boilerplate though.