Find the port that it's using.
From the Skype FAQ:
"Skype needs unrestricted outgoing TCP access to all destination ports above 1024 or to ports 80 and 443 (the former is better, however)."
I couldn't find more specific port info. It looks like it might "port-hop." There is a way to fix this, however. I've read (though not tested) that if you put a record in your DNS server that re-directs all Skype Logon requests to a null address, they'll never be able to log on.
Something to look into, anyway.
- stephan