いいじまです。

> Windows Messenger は、NAT で内側に何台が外側の IP アドレスを
> 共有していた時でも、大丈夫ですか。

はい。Windows Messenger の場合、データの通信は
        1.まずクライアントは messenger.hotmail.com:1863/tcp を叩く
        2.サーバがIPアドレスを指定するので、そのアドレスの 1863/tcp を叩き、
        　以後、その接続使い続ける
        3.ただし、ユーザー認証は https(447/tcp) で行う
        4.1863番ポートが使えないときのために、http(80/tcp)でやりとりする
        　こともできる
        5.http/https には、Windows 版クライアントの場合は IE 用のプロキシ
        　設定を流用する
        6.NATの内側の場合、サーバに指示すればNATへ出入り口のIPアドレスを
        　教えてくれる
ので、ファイヤーウォールがポート単位でブロックしていない限りは大丈夫です。
私自身もADSLルータの内側で使っています。

あるいは、あるていど高機能なブラウザ限定ですが http://webmessenger.msn.com
もあります。

【宣伝】
中継サーバー経由ですが、iモードからでもアクセスに成功しました。
http://www.ht.sakura.ne.jp/~delmonta/anmerkungen/pebrot.html

========================================================================
飯嶋 浩光 / でるもんた・いいじま   http://www.ht.sakura.ne.jp/~delmonta/
IIJIMA Hiromitsu, aka Delmonta           mailto:delmonta@ht.sakura.ne.jp