Majorgeeks have a neat little program to get rid of it once and for all!
" freeware, small file to prevent Windows Messenger from running on Windows XP. If you have SP1, you can now uninstall MSN Messenger in add emove programs and do not need this. This file should save you the trouble of manually tinkering with your registry to disable Messenger. We have tested and verified this file, but do suggest you backup your registry before applying. "
Download: Majorgeeks