To Remove Windows Messenger:
Click Start > Run... then type the following command into the box:
RunDll32 advpack.dll,LaunchINFSection %windir%\inf\msmsgs.inf,BLC.Remove
Click OK, and Windows Messenger will be removed. (Note: when I do this I sometimes get an error about unloading certain files, but just ignore it

)
As for your other problem, the only help I really found around the net was a registry fix, which is found here:
http://www.kellys-korner-xp.com/xp_tweaks.htm (scroll down to entry number 255)
Download the reg key, double-click it, and say "yes" when prompted. I recommend making a backup of your registry before you do that, though...just incase

To do that, click Start > Run... and type regedit into the box, and click OK. In the Registry Editor's toolbar, click File > Export, and make sure you select "All" when you are choosing a location to save it.
I hope that helps