Трябва да премахнеш не само програмата "Skype", но и файловете, които остават в следната папка (това е при ХР):

C:\Documents and Settings\ Твоя потребителски акаунт \Application Data\Skype\
Триеш цялата папка "Skype" след като си деинсталирал самата програма! След това си сложи някоя по нова версия!