É muito simples bloquear o skype, basta apenas bloquear o protocolo udp na saída do seu firewall para a internet.
Antes de iniciar a conexão o skype envia um pedido de atualização da lista de servidores através de uma porta udp, isso é aleatório, bloquear manualmente é inviável.
iptables -A FORWARD -o $interface_internet -p udp -j DROP
É a forma mais simples, lógico que isso pode causar outros problemas, pois você estará bloqueando todo o tráfego udp de saída da sua rede, mas daí já é questão de estudar um pouco a fundo sobre netfilter e definir com mais detalhes qual a sua necessidade.
Que é possível é, eu tenho aqui skype bloqueado e funciona 100%, tanto que tenho uma lista com excessões e alguns usuários estão liberados e o restante bloqueado.
