Etliche Beiträge befassen sich mit dem Problem aber keine Lösung hat erfolg gebracht.
Diese Vorausetzungen:
Der Uninstall hat nicht mehr funktioniert und die credentialprovider.exe und credentialprovider.dll waren ebenfalls schon gelöscht.

Wie also vorgehen:
1. Autoruns als Admin starten.
   * Ggf. auf das Registerblatt Everything wechseln.
   * Im Filter (Feld) truekey eintippen. Danach werden alle Einträge welche den Worteil "Truekey" enthalten angezeigt.
2. Alle Einträge die irgendwie McAfee TrueKey enthalten deaktivieren.
3. Computer neu starten.

4. Wenn es keine Fehlermeldungen mehr gibt Autoruns wie im Punkt 1 starten und alle Einträge löschen.
5. Registry mit Regedit.exe öffnen und auf den Root-Folder (Computer) gehen.
   * Vorab ein Backup der Registry erstellen könnte nicht schaden ;-)
   * Die Suche starten (F3) und nach truekey suchen lassen.
   * Ich hab nicht nur die Unterschlüssel sondern gleich den Ordner die mit { beginnen gelöscht. Genauso alle Ordner in dem der Name McAfeeTrueKey, TrueKeyScheduler, TrueKey vorkam. Bei letzeren hat nachschaun ob es zu McAfee gehört (EventMessageFile).
(6.) Ggf. nochmal ein Neustart.