もしかして... ICMPは通信許可されているけどUDPは通信許可されていない。
linuxのtracerouteコマンドはデフォルトでUDPプロトコルを使う。
これが原因でICMPは許可しているけどUDPを許可していないホストにはtracerouteが通らない。
tracerouteコマンドはオプションを指定すれば使用するプロトコルをICMP、TCPに変更できる。
# ICMPでtracerouteする traceroute -I ホスト
# TCPでtracerouteする traceroute -T [-p ポート番号] ホスト