>>Yes, you can: filter your primary key index on NOT DELETED(), and deleted records won't bother you. However, this has a drawback; since filtered indices won't be used by Rushmore, you will need to add a regular index on the same expression, so your queries can be optimised.
>>
>Uhhh! Are you sure about this? My experience is that a deleted record still will not permit a new record with the same primary key to be added to the table irrespective of SET DELETED status.

Yep, it works. Cut and paste this program, and check it for yourself:

SET DELETED ON

CREATE TABLE TryIt FREE ;
	(MYKEY N(5), MYDATA C(20))
	
INDEX ON MYKEY TAG NOTFORUSE CANDIDATE FOR NOT DELETED()
INDEX ON MYKEY TAG USETHISTAG

INSERT INTO TryIt VALUES (22,"HI THERE")
INSERT INTO TryIt VALUES (09,"ARE YOU WATCHING?")

DELETE FOR MYKEY=22

INSERT INTO TryIt VALUES (22, "HERE AGAIN")

Good luck!