Schadhaftes Programm hat Regkey geändert - was tun?

Poste mal so, dass wir dein Problem auch verstehen. Ob der Schlüssel mit dem Normalstart was zu tun hat, kann ich nicht gesagt werden.
Welches Betriebssystem wird verwendet?
Welche Fehlermeldung kommt beim Normalstart, bzw wie verhält sich der Rechner wenn nicht gestartet wird?
Welche Schadsoftware soll es denn gewesen sein, die diese Veränderung durchgeführt hat?
Ich kann zum Beispiel unter Windows7 diesen Schlüssel nicht finden.  
Unter XP ist der Schlüssel in der Reg. enthalten und auch OK.
Jedoch diese Angaben
HKUS\S-1-5-21-515967899-117609710-839522115-1003
konnte ich auch am XP Rechner nicht finden.

Dieses von Dir genannte "Startup" hat absolut nichts mit dem Systemstart zu tun. Dieser Bereich der Registry beschäftigt sich mit dem Autostart von CDs, Festplatten und Sticks.
Um Hilfe zu erhalten, sind diese Angaben wichtig:
- welches Betriebssystem verwendest Du
- was (konkret) wurde gemacht, bevor die Störung eintrat
- welche Maßnahmen hast Du selbst bisher durchgeführt.
Ist das bekannt, kann man versuchen, zu helfen.

Jürgen

PS: 

bringt es was den schlüssel einfach zu löschen?

HKU\S-1-5-21-515967899-117609710-839522115-1003\Software\Microsoft\Windows\CurrentVersion\Explorer\Shell Folders\...Eintrag im rechten Teilfenster "Startup" unter Wert "C:\Dokumente und Einstellungen\Alexander\Startmenü\Programme\Autostart" ist völlig korrekt.Einstellung bei XP.Bei Vista und Windows 7 müsste ich erst mal nachschauen.Hier sollte kein Fehler sein.Wie kommst du auf diesen Schlüssel? Der ist sicher nicht für deine Probleme schuld!
Es heißt so HKU (HKEY USERS) nicht HKUS !
Schließe mich der Meinung von @ Jüki an ! Finger weg von der Registry,wenn nicht genügend Kenntnisse vorhanden sind!
Kannst das hier mal versuchen.
http://www.windowspower.de/Systemwiederherstellung-bei-Windows-XP-im-abgesicherten-Modus_860.html

Die letzte und wahrscheinlich vernünftigste Alternative,wird die Neuinstallation sein!

Betriebssystem ist Windowy XP Prof.
Ja gut hab mir schon gedacht, dass die Einstellung doch ok sein müsste, macht ja an sich sinn. Systemwiederherstellung usw. geht leider nicht.
Ich weiß halt dass das Programm angeblich was an dem Schlüssel gemacht haben soll laut Comodo Internet Security.
Hier sind die Meldungen:
http://imageshack.us/photo/my-images/710/neubitmapn.png/

Programm war folgendes:http://www.filestube.com/d511091b13dc936a03e9,g/Guitar-FX-BOX-2-y-3-Full-Version-by-ZANTHO.html

Naja ich denke ich werd wohl formatieren müssen.
Beim hochfahren krieg ich nen Blue Screen nach dem Ladebildschirm für Windows, was dasteht kann ich leider nicht genau lesen, weils zu schnell geht, aber auch irgendwas von nem Schlüssel. Danach resetet einfach der Pc und fährt wieder hoch.

Bei diesem Problem wird man nicht viel machen können.Neuinstallation ist die beste und sicherste Wahl.

Mit F8 beim Start im Menü den Neustart bei blue Screen abschalten Dann kannst du auch lesen warum nicht gestartet wird.
Naja nicht lizenziertes Programm usw. dürfte aber ein Treiberfehler sein. Schon versucht das Programm zu deinstallieren, biete es nicht gerne an, aber in diesem fall wohl doch ein Helfer, Ccleaner installieren und Registry säubern und normalen Durchlauf starten. Dann versuche wieder zu starten.
Denn im abgesichertem Modus kannst du hochfahren, oder?

Ok also der Blue Screen bringt: c000021a (schwerer Systemfehler)
Der Systemprozess Session Manager Initialization wurer unerwartet beendet. Staus 0x0000022 (0x00000000 0x00000000). Das System wurde heruntergefahren.

zur Deiinstallation.. ich hab erstmal versucht das Programm einfach zu löschen, hätte ich nicht machen sollen, hatte leider nichts gebracht. Habs dann noch ma neu installiert und dann wieder deinstalliert, hat dann auch nichts mehr gebracht.
Im abgesicherten Modus kann ich hochfahren.

eine Möglichkeit noch, bevor Du am Besten wie Exit es schrieb, eine Neuinstallation machst:

Starte im abgesicherten Modus und führe einen Systemwiederherstellung durch, Zeitpunkt, bevor der Fehler auftrat ( vielleicht klappt die SWH im abgesicherten Modus ).

Systemwiederherstellung hab ich schon versucht, hab aber kein Wiederherstellungspunkt, kann ich also leider nicht nutzen.
Trotzdem danke für die Tipps

hab aber kein Wiederherstellungspunkt,

hab gar keine erstellt, und bei den standardeinstellungen war automatischen erstellen wohl nicht an

installiere neu und zwar nach Jükis Methode und vergiß nicht ein Backup auf einer anderen Partition zu machen, das erspart Dir im Falle eines Falles Ärger und Zeitaufwand:

Windows XP Neuinstallation

und bei den standardeinstellungen war automatischen erstellen wohl nicht an

Ist vielleicht auch besser, eine Neuinstallation. Nur ich würde dir anraten auch die Partition zu löschen und neu erstellen.
Der 022 Fehler kann von einem Virus stammen welcher die Windows-Logon.exe manipuliert hat, aber auch von einem Fehler in den NTFS Rechten.
An und und für sich wäre noch eine Möglichkeit der Reparatur mit der R Konsole möglich. Zuerst chkdsk /r /f ausführen danach fixmbr und fixboot ausführen.
Dies mit der Winlogon.exe habe ich schon öfters mit einer neu Installation dieser Datei gemacht.   

backup werd ich auf ne externe machen, hatte mit mehreren partitionen eig immer probleme, der explorer kam damit gar nicht klar ist oft abgestürzt usw. was bei einer partition nie der fall war. hat jmd ahnung woran das liegen könnte?

An fehlerhafter Hardware? (Festplatte)
Es gibt tausende User, die ihre Festplatten in mehrere Partitionen geteilt haben - bisher las ich solche Vermutung zum ersten Mal, daß der Windows-Explorer derartige Fehlreaktionen auslösen würde.