Você pode adicionar o seguinte índice para indexar apenas colunas não anuláveis:
create table tblEmployee(col1 int, col2 int)
go
create unique nonclustered index idx_col1col2_notnull ON tblEmployee(col1,col2)
where col1 is not null and col2 is not null
go
--This Insert successeds
insert into tblEmployee values
(null, null),
(null, null),
(1, null),
(1, null),
(null, 2),
(null, 2)
--This Insert fails
insert into tblEmployee values
(3, 4),
(3, 4)
