Dentro do seu DNS interno (do AD) crie um registro do tipo SRV conforme abaixo:
_sipfederationtls._tcp.seudominio.com.br
Porta 5061
Host offering this service
complete com o IP externo do seu Skype EDGE
Olhe no cliente se os contatos deixam de apresentar presença desconhecida.