>You're shifting the problem from the Primary key (surrogate) to the candidate key (meaningfull). In your case, you should filter the candidate index on !deleted().

True enough. I like recalling the deleted record. Or overwriting the Candidate key field with a surrogate key. Or, not use a candidate index at all and enforce uniqueness with a biz rule. The latter is my personal preference.