MSN Messenger will have add remove short cut... but i think u are refering to Windows Messenger...
Do this, Go to Add Remove Progras Window under Control Panel now Click the button in right side navigation bar called Add/Remove Windows Componemt...
*img406.imageshack.us/img406/6855/untitledus1.jpg
It will launch the configuration Window, there scrool down to the lowest end to find Out Look Express and Windows Messenger, so unchcek their boxes and Click next to finish the process...
*img406.imageshack.us/img406/8216/untitledug2.jpg
note what Windows does is actually removes the short cut of Putlook from ur system... the actual core will remain in the system....