{20D04FE0-3AEA-1069-A2D8-08002B30309D} is the CLSID for "My Computer".
Those keys not being there is very strange. Since they should be added (among some other stuff) when you installed Messenger.
At this moment I'm out of clues and can only think that something goes realy wrong when you install Messenger, or that your Vista installation has some serious issues. You do have full admin rights, no? And do other special folders work properly (eg: Briefcase, My networks, My documents, Control Panel, etc)? You also closed Explorer (changes wont take any (good) effect unless you close and reopen Explorer)?
So, the only thing I could suggest is to remove everything again so that you don't have a messed up folder. I'll continue to search for some clues and will post back if I found one. Though, I hope that someone else could help you though since I'm out of ideas.
At last resort you might also want to contact WLM support:
https://support.live.com/default.aspx?productkey=wlmessenger
/ 
