< SNIP >

>You can also change the key value before deleteing a record. FOr example a numeric key could be made negative when the record is deleted.
>

Changing the key works, but making it negative doesn't, for the simple reason that if you ever recycle a key twice, there will be two identical negative values...

>The index could be made a composite key that includes the deleted status as part of the key.

Same problem.