Happens to me here as well, but it's not related to the network. A
Tiger machine was working fine one day and the next it just refused to
connect. Another machine with Tiger, same MSN, on the same network,
connects just perfectly.
After a clean install, it keeps the same way.
No solution in sight :-(
I think this is not related to Messenger, though. Maybe machine bound.