ulxo, даже и не буду спрашивать, зачем вам понадобилось удалять (переустанавливать) Мессенджер?

Значит так, по-порядку ))
Первое. Программы таким способом как вы описали никто и никогда не удаляет. Программы удаляются двумя способами: с помощью специального ярлыка в меню Пуск -> папка программы -> Деинсталлировать (удалить, возможны варианты), или же через Панель управления -> Программы и компоненты (если такого ярлыка не оказалось в меню Пуск).
Второе. Когда вы удалили ярлыки на Мессенджер (и другие) из меню Пуск, то сама программа осталась, она некуда не делась, поэтому установщик и говорит, что программа у вас установлена.
Чтобы удалить программы Windows Live, выполните указанные ниже действия.
1. В ОС
Windows XP нажмите кнопку
Пуск, а затем щелкните
Выполнить (или нажмите комбинацию клавиш
Win+R).
–или–
В ОС
Windows Vista нажмите кнопку
Пуск, а затем щелкните в поле
Начать поиск (или нажмите комбинацию клавиш
Win+R).
2. Введите
appwiz.cpl и нажмите клавишу
Enter.
3. Щелкните
Основные компоненты Windows Live, а затем нажмите кнопку
Удалить или
Удалить/Изменить. При появлении запроса нажмите кнопку
Продолжить.
4. Нажмите кнопку
Удалить, а затем нажмите кнопку
Продолжить.
5. Установите флажки рядом с программами Windows Live, которые необходимо удалить, а затем нажмите кнопку
Удалить.
6. Следуйте инструкциям на экране.
Теперь вы можете заново попробовать установить программы Windows Live.