Try registering the necessary .dll files:
Click Start / Run / type in
(or Copy/Paste);
regsvr32 Dssenh.dll /sDo the same, for each of the following:
regsvr32 Gpkcsp.dll /s
regsvr32 Slbcsp.dll /s
regsvr32 Sccbase.dll /s
regsvr32 Softpub.dll /s
regsvr32 Wintrust.dll /s
regsvr32 Initpki.dll /s
regsvr32 Rsaenh.dll /s
regsvr32 Mssip32.dll /s
regsvr32 Cryptdlg.dll /s
regsvr32 Msxml3.dll /s
Some times, when trying to register
Msxml3.dll, you will receive a message that it has failed.
If you receive this message, go to
Microsoft XML Parser (MSXML) 3.0 Service Pack 7 (SP7), scroll to the bottom, download, and install
msxml3.msi.
Reboot, and try Messenger again.