Breno,

A solução que costumo adotar é a seguinte: colocar em chaves primárias ou candidatas um filtro para registros deletados.

Exemplo:

* Vou criar uma tabela e definir uma chave candidata
CREATE TABLE testtable (id i )
INDEX ON id TAG id FOR !DELETED() CANDIDATE

* Vou inserir alguns registros
INSERT INTO testtable VALUES (1)
INSERT INTO testtable VALUES (2)
INSERT INTO testtable VALUES (3)

* Agora vou deletar o registro com id = 1
DELETE FROM testtable WHERE id = 1

* E em seguida inserir novamente um registro com a chave id = 1
INSERT INTO testtable VALUES (1)

A única ressalva que faço é a seguinte, indices com cláusula FOR não são utilizados para otimização de acesso (Rushmore).