>Anyone have any good ideas when a user adds a new record to a table, that has the same primary/candidate key of a previously deleted record.

Gamble,

I only use surrogate primary keys so this never happens on the PK. For a CK you could add the FOR condition of NOT DELETED() to the candidate index command.