I don't know much about live messenger but perhaps you have to port forward. First figure out which ports you need first. Prolly can google. Then log into your router and under the dhcp tab set your computer to static. Then go to advance port forward and just give it a name and tell it to forward that port to your computer on the same port.
If you don't have to port forward sounds like a firewall issue.