Uniqueness is enforced across deleted records also. The setting of SET DELETED ON doesn't make any difference. The reason for this is because a deleted record can always be RECALLed.

This is another argument for "surrogate" keys. In other words, your primary key should be a meaningless key used behind the scenes and not "seen" by the user. Your current id field you're using can either have uniqueness enforced by code in the form that you're inputting data with, or else you can create a candidate key with a NOT DELETED() condition placed on it.

--Brad