Solution 1:
filter the primary key
(but this removes the index from the directory of the usable indices from the optimization)

ALTER TABLE ... ADD PRIMARY KEY ProductID FOR !DELETED() TAG PK_Index

Soluzion 2:
replace the deleted record primary key with a not valid value.
you can define a deleted trigger for do this.