会社からSkypeへのログインが出来たり、出来なかったりしてましたが、ようやく解決方が分かりました。単純に、幾つかの外向けのTCPポートを空ける事で解決しました。
　ただ、なぜ外向けのTCPポートを空けたら解決するのか、折角だったので、Skypeの技術について、少し調べました。特にファイアーウォールの内側にいる場合に、どうやっているのかが気になりましたので、その辺りを中心に。

　結構、難しい事をやっているみたいで、まず、最初にこれに目を通しました。
　「Skypeはファイアーウォールをどのように通過しているのか？」
　これを見ると分かりますが、Skypeというのは、純粋なP2P技術ではなく、第三者である別のノードの助けを借りて、F/W内同士の通話接続を確立しているようです。一旦、確立されると両ノード間で直接コミュニケーションが出来るようになります。その際に、使っている技術が「UDP Hole Punching」だそうです。ただ、本当にこれを使っているかどうかは定かではありません。また、ここには残念ながら、ログインプロセスについての記述はありませんでした。で、もう少し調べてみると、以下の文献があるようです。
　「An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol」　
　Salman A.Baset and Henning Schulzrinne (pdf)
　この論文を見てみると、更に深くSkypeの技術について、調査しています。この論文にあるFigure1を見ると、Skypeネットワークというのは三つのタイプのノードから構成されているようです。
　１）Skype Login Server
　２）Super Node
　３）Ordinary Host(Skype Client)
　やはり、純粋なP2Pではなく、Login情報などはCentralizedサーバ形式なようです。で、Firewall内にいるユーザが何の設定も無しに通信が出来るようにSuper Nodeと呼ばれる仲介役を使って、P2P接続を行うようです。ここのミソはSuper Nodeというのが、Decentralized形のネットワークを構築しており、Super Node同士で相互に通信しているという事です。つまり、一般に使われているSIPサーバを使ったIP電話と異なり、ネットワーク的に非常に強固という事です。どこか一台のサーバが死のうが、サーバ負荷が発生しようが、グローバルIPを持ったSuper Nodeが他にあれば、そこに負荷を分散させて生きます。死なないネットワークというわけです。
　
　なるほど、なるほど。これでSkypeのネットワーク像が少し分かりました。では、本題に戻って、なぜ、外向きのTCPポートを空けたら、ログイン出来るようになったのか？
　そこを紐解く鍵は、ログインプロセス、及び、Super Nodeへの登録プロセスにあります。F/W内にあるSkypeクライアントがログインする場合、STUNプロトコルというのを使って、NATやFirewallのタイプを判断しています。その際、よく分からないんですが、色々なTCPポートを使って通信を繰り返しており、その後、接続を確立しています。試しに、私もDumpしてみたんですが、80/443番の番号以外は、ランダムでTCP番号を選びながら、パケットを送っています。私の理解力では、このぐらいまでしか分からなかったんですが、とりあえず、Super Nodeに対して、Firewallの環境や、クライアント情報をRegistする為に、外向けのTCPポートの開放が必要なようです。
　ちょっと中途半端な感じですけど、要はTCPポートを空ければ、スムーズに接続出来るようです。ただ、そうしなくても、80/443が空いている場合はうまく行くこともあるみたいです。ネットワークのコンディションやFirewallのタイプによるのかも知れません。よく分かりません。
　その他、興味のある方はこの辺りが参考になるかと思います。
　http://www.skype.com/help/faq/filetransfer.html
　http://toremoro.tea-nifty.com/tomos_hotline/2004/12/skypeskype_1.html
　http://www.asahi-net.or.jp/~AE5T-KSN/d/200412.html
　http://www.dodgson.org/omo/t/?date=20041219
　※ちなみに、眞崎の理解した範囲で書いていますので、内容の信憑性については、一切保障出来ないです。