To remove Skype (or most programs) completely, check the Program and Features, find it and uninstall this way (even though you said you did this).
After this is done do a simple search in C:\Program Files and C:\Program Files(x86) if it exists for any Skype folders. If you find any, delete those too.
Search in your registry for any Skype components. Press windows key + r then type 'regedit' and click ok. Navigate to HKEY_CURRENT_USER\Software\Skype and delete this entire folder.
Alternate method:
Download, but don’t run this installer for the latest version.
Using the procedure described here,
http://community.skype.com/t5/Windows-archive/How-to-update-Skype-without-using-any-Skype-installer/m-p/707359
extract the Skype.exe file from the SkypeSetup.msi file and replace your currently installed Skype.exe with this new Skype.exe file. You will be now running the latest Skype version.
After this, there should be no parts of Skype remaining.