Well, for lack of other options, if you want you can try and do this:
This might help, but it might not.
1. Make sure that you are using Windows Live Messenger version
14.0.8064.206
2. Open the messenger folder. Commonly this is C:\Program Files\Windows Live\Messenger
3. Make a copy of liveNatTrav.dll just in case something goes wrong.
4. Open liveNatTrav.dll (from the messenger folder) in a hex editor.
If you don't have a hex editor, The editor I use is
Notepad++ with the
Hex Editor Plugin
5. At offset 0x00023FCA, you should see EB 36. Change this to EB 3A.
6. Save the file and try messenger again.
If it still freezes, then it's a different problem than I think it is, and you can put the original liveNatTrav.dll back, but this trick worked for me, so it might help you too.
/ 
