I stumbled across this fix via a web search in the Live Messenger Blog about a different error code. It worked for me on Windows Vista.
1.) Close Messenger. Go into Task Manager and ensure that the “msnmsgr.exe” process is not there. If it is, kill the process.
2.) Navigate to C:\Users\<YourUserName>\AppData\Local\Microsoft\Windows Live Contacts and delete the entire contents of the folder.
3.) Restart Windows Live Messenger. Voila!
There is another issue I found where the standalone installer for Messenger fails with a message like “could not open key…”. One fix for this is to navigate to the C:\Program Files\Windows Live\Messenger folder and DELETE the msnmsgr.exe executable if it is there.
ReallyReallyDumb Exception Messages Department
I think it was Donn Felker who first tweeted about this, but I didn’t believe it until I got one myself: