Программа!

Вообще это очень странно, что в Меню "Пуск" ярлыки есть, но при этом Вы удаляли спец.программой(а не просто удалением папки из проводника).

Возможно у вас удалилась версия старшая, а младшая так и осталась на комьютере? Ярлыки-то к какой версии ведут?

А по месту... Возможно такое решение: новая версия могла как-бы на чуть-чуть увеличиться, т.е. при её удалении действительно не особо много места освободиться.