To solve this issue, add another field called (say) DeletionId that defaults to zero and populate that field with the id of the record when the record is flagged as deleted. Include this field in the unique index.
For example, assume the following table
create table MyTable
MyTableId int identity(1,1) not null
,MyTableName varchar(100) not null
,StatusId smallint not null
,DeletionId int not null
constraint DF_MyTable_DeletionId default 0
,constraint PK_MyTable primary key (MyTableId)
,constraint UK_MyTable_MyTableName Unique (MyTableName, DeletionId)
To flag as deleted (if 2 means deleted and 5 is the id of the record):
update MyTableName set StatusId = 2, DeletionFlag = MyTableId where MyTableId = 5
By using the DeletionId it is possible to have many deleted records in the table with the same name but only one record in the table that is not deleted with the name. That is, the undeleted name is unique.