First of all remove any patches and add-ons you have installed then try if all works as should. This also includes, but is not limited to, Smiley Central, SweetIM etc.
If you found all is working fine you can add them back one by one to find which causes it. If you got Messenger Plus! Live installed also verify that none of the scripts you have are interfering, doubtful they would but you never know... (this is also important to test before you submit any bugs about Messenger Plus! Live).
Error message 80072745
If you get this constantly try the following:
- Go into your router/connection (LAN) configuration
- In the DNS Address section (Internet-protocol TCP/IP) do not use 'Get Automatically from ISP', instead use static IP adresses for the Primary and Secondary DNS (your provider can tell you which to use if none are there already)
If it still isn't working as should after that:
Source: Inside Windows Live Messenger - We hear you!
Having Connection Problems?
If you’re having problems connecting to Messenger and/or sending IM’s, we encourage you to try the some of the following suggestions:
1. Make sure that your firewall is properly configured to allow Windows Live Messenger 8.1 to function properly.
Behind a corporate firewall: The 8.1 client uses far more web services, and it is possible that the network administrator for the corporate firewall will need to put a few more URLs on their web address white list. The client needs to send web requests to “*.hotmail.com”, “*.live.com”, and “*.msn.com”. (The asterisk (*) is a “wildcard” character meaning that anything can come before “live.com”.) Your network/ firewall admin will understand this jargon if they see it.
On your PC at home: Many personal firewall products learn what a client does on the network, sometimes asking the user for permission to allow the applications to access the Internet and then remembering these answers. When the new client changes its network behavior, some personal firewall products don't learn fast enough about how to let the client function properly on the network. To test this you can temporarily turn off your firewall and see if you can sign-in. Be sure you turn the personal firewall back on after your experiment. If you can sign-in, then it is likely that your personal firewall needs to reconfigure itself. Many products allow you to see the list of filters it is using, and by removing the filter entries for messenger (or msnmsgr.exe) you can force the personal firewall to re-ask you for permission to grant the required network access to the new 8.1 Messenger client. Sometimes you have to let the client fail a few times while the firewall is learning, and then restart the client.
2. Try to using the Connection Troubleshooter (you don’t have to login to Messenger to do this). You can find it in Messenger -> Tools -> Options -> Connection tab
3. If you are using a proxy server, click on ‘Advanced Settings’ and configure the proxy settings.
4. If IE is NOT set as your default browser, launch IE (you don’t have to set it as default) and visit any webpage to make sure that the internet connectivity and network configurations are properly set.
Is Messenger Crashing?
If you are using Windows Vista, you may encounter crashes if you don’t have the latest version of Adobe Flash installed. You can install the latest version of Adobe Flash at
http://www.adobe.com/shockwave/download/download....Flash&promoid=BIOW.
If you have a computer manufactured by Acer, you may be using Acer eDataSecurity software. Please upgrade to the latest version at
http://global.acer.com/support/winvista/t-faq.htm.
Error Codes
For more information on specific error codes, please visit the
Messenger Support Space. You’ll find lots of information and troubleshooting tips there.
More Updates to Come
Check back here (Inside Live Messenger Space) often for updates on other issues. If you’re having a problem, please head over to the
newsgroups and post there!
Edit: updated for error message 80072745
/ 
