Damit hast Du Skype aber nicht deinstalliert, sondern vermutlich nur den Link im Kontextmenü, Skype bleibt aber auf dem PC.
Installier Skype doch nochmal neu. Möglicherweise kommt der Installer mit deinem Stand klar, richtet alles korrekt ein, sodass danach das Deinstallieren wieder funktioniert.
Vielleicht gibt's auch einen eigenen Uninstaller von Microsoft, den Du direkt starten kannst.
Alternativ kannst Du versuchen, ob der Installer selber per Kommandozeile und der Option "/uninstall" Skype entfernen kann, Windows macht oft auch nichts anderes.
Wenn "/uninstall" nicht geht, schau nach Hilfe-Optionen ("help", "?", Slash oder Komma davor, etc.), vielleicht heißt der Befehl einfach nur anders, die Hilfe-Option sollte das dann auflisten.
Ansonsten hab ich nur das gefunden:
answers.microsoft.co...a3-b1fe-c7ad84a7b488
Sowohl Die Kommandozeile als auch Powershell kann Programme mit Systemrechten ausführen, allerdings sollten Admin-Rechte eigentlich völlig ausreichen.
Wie Du an die Rechte kommst, dafür gibt's online endlos viele Anleitungen.
Hilft das alles nix, kannst Du noch manuell auf die Suche gehen.
In den üblichen Programme-Ordner oder unter AppData findet man meist diverse Ordner, möglicherweise in einem "Microsoft"-Unterordner.
Ansonsten kannst Du auch in der Registry suchen lassen, vielleicht findest Du da noch ein paar Eintrage und vielleicht auch einen Ordner, wo noch ein paar Dateien gelöscht werden wollen.
In der Registry solltest Du aber nicht einfach so wild herum löschen, um Zweifel kannst Du aber per Rechtsklick exportieren, das lässt sich dann wieder importieren, wenn Du Probleme hast.
Und CCleaner:
Ich halte von solchen Tools nichts - bitte nicht benutzen.
Die versprechen dir tolle Dinge (z.B. Registry aufräumen), können nicht wirklich garantieren, dass sie dabei nichts kaputt machen.
Es wäre also durchaus denkbar, dass jaenicke Recht hat und der CCleaner deine Skype-Uninstall-Informationen "aufgeräumt" hat und es deshalb nicht mehr deinstalliert werden kann.
Und der CCleaner macht beim Deinstallieren vermutlich auch nichts anderes, als auf die selben Uninstall-Informationen zuzugreifen - weshalb der auch versagt.