Check whether the offending messenger program is 'Windows Live Messenger', or 'Windows Messenger'.
XP bundled 'Windows Messenger' when it shipped, and it was an utter pig to remove.
( Google 'XP remove windows messenger' ).
Then, there was the MSN-branded MSN messenger, which was installable and sometimes un-installable.
Finally, there was Windows Live Messenger, which is part of the Windows Live suite of add-on crapware, which should be removable.
The removal process is different in each case.