Also, delete the MSN Messenger folder in the registry.
After uninstalling and deleting the Program Files folder, go to:
Start > Run > regedit > Locate to the following folders and right click, delete:
- HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\MSNMessenger
- HKEY_CURRENT_USER\Software\Microsoft\MSNMessenger
Be careful that you don't delete anything else in the registry, just the MSNMessenger folders.