After formatting and installing Windows again, make absolutely sure you have also installed all the service packs, hotfixes and patches for Windows.
For this you _must_ go to
http://www.windowsupdate.com/ and follow the instructions. After updating you _must_ visit that site again and again until there are no fixes anymore to install...
After that, make sure you reinstall Messenger (and Messenger Plus) properly.
PS: and don't forget to reboot after each new install...
/ 
