Hai provato con Messenger 6.0?
Io con le versioni precedenti avevo risolto installando un programmino "eNat for Messenger", ma la versione 6.0 funziona perfettamente sotto NAT.
Ciao