This combination seemed to fix the problem:
1. Make sure that there is a messenger.msi file in the C:\WINDOWS\Installer folder.
2. If it is not present use the 'Search' function of Windows by tapping F3 and search for the file on your Windows folder.
3. Copy the file into the C:\WINDOWS\Installer folder.
4. Fire up Windows Messenger and log in.
5. If there is a new version available, a message will prompt. Follow the onscreen instruction.