Como estão as suas regras?
Você tem uma regra que libera todo o tráfego para HTTP e HTTPS para todos os usuários? Se sim, tire o HTTPS e faça um teste. Caso o Skype não conecte, crie outra regra para o HTTPS e defina os endereços que podem ser acessados via HTTPS.
Lembrando que, uma regra que libera All Outbound Protocols, vai estar liberando TODOS os protocolos que existem no ISA, caso não esteja lá o acesso vai ser negado, então o mais provável é que o Skype esteja utilizando a porta 443 para se conectar.
Portas altas, acima da 1024, que são as geralmente usadas pelo Skype (aleatoriamente) não serão usadas ao menos que você use a opção Port Range em alguma outra regra.
Dê uma olhada nesse link:
http://forums.isaserver.org/m_2002000643/mpage_1/tm.htm
O protocolo dop skype usa um túnel HTTP para se conectar e como ele é baseado em uma rede multimesh é impossível bloquear por hosts, pois ele não usa um range específo, porém em uma versão específica do skype que você vai encontrar no link acima ele usa uma assinatura HTTP que você pode usar para bloquear o Skype, não funciona com todas as versões, infelizmente.
