Managing deleted entries in large database table
Partitioning is particularly useful for this.

See https://stackoverflow.com/questions/12929624/partitions-and-update for an example of how an update can cause rows to be moved to a different partition.

This enables you to keep your table structure as it is, including almost all existing code, while queries for active data will only query the appropriate parition.