> I've seen tables where 50%-70% were soft-deleted, and it did affect the performance noticeably.

At that point you should probably investigate partitioning or data warehousing.