I would treat the current "deleted" column as a "generation" column. Generation zero would be the current or active generation. When you wish to "retire" a row, set the generation to 1 + Max(generation) for the current ID column, then add a new generation zero row for the ID value.

You can then declare a unqiue constraint on the combination of the ID column and the generation column. No two rows can have the same pair of values, so only one row with a given ID value can have a zero generation to make it current.

The generation values have to be unique, but that's fast and easy to manage. This lets the database guarantee (by the unique constraint) that code has to behave.

-PatP