ＩＣＱ側の設定しわすれが考えられますね。
以下のページを参考にしてください。

ｆｉｒｅｗａｌｌ道場
http://www.atw.ne.jp/~pockets/cyber/icq/guide/firewall/firewall.html

〔ツリー構成〕

┣【401】 オフライン状態からメッセージが来ます・・・ 1999/6/20(日)01:29 RiRi (655)

┣【402】 re(1):オフライン状態からメッセージが来ます・・・ 1999/6/20(日)01:43 まゆう (227)

┣【403】 re(2):オフライン状態からメッセージが来ます・・・ 1999/6/20(日)02:03 RiRi (119)

┣【411】 re(3):オフライン状態からメッセージが来ます・・・ 1999/6/20(日)03:00 まゆう (205)

┣【414】 re(4):オフライン状態からメッセージが来ます・・・ 1999/6/20(日)04:19 まゆう (108)

┣【422】 あと考えられるのは 1999/6/20(日)15:42 まゆう (167)