Er... that is not MSN Messenger, that is Windows Messenger. You did not
remove it, you just told it to remove the shortcut from the start menu. Look
under C:\Program Files\Messenger and it is still there. MSN Messenger is a
program that superceeds Windows Messenger and you have to download it
manually.