Unbekannte Programme versuchen, auf das Internet zuzugreifen - Ursprung unbekannt

Gekautes

Hallo Trojaner-Board,

da sich mein Betriebssystem beim Systemstart seit einigen Tagen öfters mit einer Meldung wie (im Wortlaut) "xxx.exe versucht, eine Verbindung zum Internet herzustellen. Zulassen?" (wobei der Name der Anwendung aus kryptischen Buchstabenfolgen wie "abyqc" oder "poafexmy" besteht) meldet und das auch nach dem Beenden der betreffenden Prozesse über den Task Manager sowie dem Entfernen der betreffenden Dateien aus dem AppData\Local-Verzeichnis immer wieder passiert, brauche ich wohl etwas mehr professionelle Hilfe.
Einen Virenscan über AntiVir sowie Anti-Malware lieferte keine Ergebnisse. Auch das mit meinen Laienaugen manuelle Durchforsten diverse Verzeichnisse auf meiner C-Partition brachte nicht den erhofften Erfolg.

Meine eigenen Recherchen brachten nur folgende Erkenntnisse:

Ein Registry-Scan mit dem CCleaner findet immer wieder den folgenden Fehler:

Ungenutzte Datei-Endungen {80b8c23c-16e0-4cd8-bbc3-cecec9a78b79} HKCR\{80b8c23c-16e0-4cd8-bbc3-cecec9a78b79}

Ein Löschen dieses Schlüssels ist nicht möglich, weder über den CCleaner noch manuell über den Registry-Editor (Fehlermeldung: "[...] kann nicht gelöscht werden. Fehler beim Löschen des Schlüssels."
Über den MSConfig-Dialog waren diverse dieser oben genannten Anwendungen im Systemstart festgelegt (und bestehen auch nach der Löschung weiterhin als anwählbarer Punkt).
Die erste dieser Anwendungen befand sich in dem Verzeichnis C:\Users\Gekautes\AppData\Local\SkypeM. Aus diesem Grund habe ich zuletzt Skype deinstalliert, da ich davon ausgehe, dass es unter Umständen (wie auch immer) an diesem Programm lag. Nachdem aber nach einem weiteren Neustart wieder die oben beschriebene Meldung auftauchte, scheint das auch nicht geholfen zu haben.

Nach dieser hoffentlich ausreichenden Beschreibung wende ich mich nun an die kompetente Hilfe hier im Forum und bitte euch darum, die angehängten Log Files durchzusehen. Vielleicht stellt man dort fest, ob etwas nicht stimmt und wie das Problem eventuell zu beheben ist.