There is a new version (minor revision) of Windows Messenger. The installer used by Microsoft has had loads of problems, many of which I've experienced myself.
One Registry related problem I had related to permissions which had to be given before the installer could make the necessary registry changes. click here
That may help.
As far as registry cleaning is concerned, I would treat CCleaner as a tickle with a duster. Eusing Free Registry Cleaner is likely to do a more thorough job. click here