Enforce a column as unique based on another column value
When you have a unique constraint that you want to apply to only a subset of rows, you can enforce this using a unique, filtered index. The index that seemed to work for you in this case is:

CREATE UNIQUE INDEX [UNQ_SampleTable_Code]
  ON dbo.[SampleTable]([Code])
  WHERE   ([Deleted] = 0);


This ensures that only one distinct value of Code can exist for rows where Deleted is 0, but duplicates can exist where Deleted is 1. Typically this will also help the performance of some queries, since you will often be interested in only the active rows (and not the soft deletes), but you may want to consider adding columns to the INCLUDE clause if this doesn't cover queries (SQL Server may choose to scan the clustered index, or a different index, if lookups are deemed too costly).