It appears your problem is well-documented. Here is one of several Google hits I found:
http://www.bigblueball.com/forums/msn-messenger-support/17420-error-code-1601-1603-solutions.html
The situation is that for as wide-spread as the problem seems to be, there is no magic-bullet cure. Which means you are going to have to do some trial & error.
Read the whole of the posts in the link provided, and see if you can find a situation that most-resembles yours and try the fix suggested. Note that there are 12 pages of posts. In these situations, I always read the thread forward thoughout, then backward and try the latest fixes first.
Make note that certain AV programs may interfere with the installation, such as Ad-Aware and also I would assume Spybot as both prevent registry changes. It is for this reason that I would always attempt a new install in Safe Mode, no matter what other steps a particular suggestion may be.
The only other thing I can think of to add is to make sure that the MSN installation is completely removed before reinstalling it, as frequently corrupt elements of the bad installation do not always get over-written during the reinstallation process. Often, a re-boot in between the uninstallation and the reinstallation is a good idea.
And as general steps, it is always good to:
run chkdsk
update virus definition files & run malware scans
make sure Windows Update is current
before embarking on any major operation, as these general fixes can sometimes solve the problem without you having to know exactly what the problem is.
Good Luck
Girderman
