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...
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...
note what Windows does is actually removes the short cut of Putlook from ur system... the actual core will remain in the system....