Usando o SQL Server 2008, você pode criar um índice filtrado:http://msdn.microsoft.com/en-us/library/cc280372.aspx. (Vejo que Simon adicionou isso como um comentário, mas achei que merecia sua própria resposta, pois o comentário é facilmente perdido.)

Outra opção é um gatilho para verificar a exclusividade, mas isso pode afetar o desempenho.