You can go here and download a VBS script that will take care of it. I used it on my laptop, haven't had a problem since. If you are not comfortable using the VBS, You can do it manually. It's under Utilities for XP at the bottom, look for one called Disable or Remove Messenger from Windows and OE.
http://www.kellys-korner-xp.com/xp_tweaks2.htm#gen
(this was taken from the same site as above)
Tip: Easiest method to disable Messenger: C:\Program Files\Messenger and either rename the Messenger folder to
something like "MessengerOLD" or just move it.
Remove Messenger from XP
Start/Run/RunDll32 advpack.dll,LaunchINFSection %windir%\INF\msmsgs.inf,BLC.Remove
Disable Messenger
Start/Run/gpedit.msc/Admistrative Templates/Windows Components/Windows Messenger. Alter your settings in the right pane. (For Pro)
Stop Windows Messenger from Auto-Starting
Simply delete the following Registry Key:
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Run\MSMSGS
Uninstall Messenger
You have to edit sysoc.inf (located in /WINDOWS/inf). Under [Components] you should see the following line:
msmsgs=ocgen.dll,OcEntry,msmsgs.inf,hide,7. Take the word 'hide' out of the line, and it should look like this:
msmsgs=ocgen.dll,OcEntry,msmsgs.inf,,7. Exit and save.
Go to Add or Remove Programs, and click on Add/Remove Windows Components. There you should now be able to uncheck the MSN Messenger Service, and by clicking Next it will uninstall.