Sconfitto da uno spyware

Per la prima volta in anni di onorata carriera sono stato sconfitto da uno spyware; il bastardo in questione è desktop.exe, una barrettina di ricerca che si è piazzata sul desktop di un utonto (C:\Windows\isrvs\desktop.exe)
Normalmente la seguente tecnica ha sempre funzionato (sistemi 2000/xp):

• apro il registro con regedit, faccio un backup completo, controllo le chiavi Run, RunServices, ecc. in HKLM e HKLU e rimuovo tutte le voci sospette
• disabilito il ripristino di sistema su XP
• ammazzo i processi sospetti nel task manager
  
• aggiorno l'antivirus, eseguo la scansione sulla cartella Windows e Documents And Settings
• installo Spybot S&D e faccio la scansione completa
• riavvio il sistema

Ebbene, in questo caso la procedura non ha funzionato: non riesco a cancellare le voci di registro presenti nella chiave RUN. Windows mi avvisa che non ho il permesso di cancellare quei valori.
Ho provato a creare nuovi utenti, ad avviare regedit come operazione pianificata (ho letto un suggerimento in una delle mille pagine disponibili sull'argomento), a scaricarmi XSoftSpy (rileva il problema ma riesce ad eliminarlo): tutto inutile.

Il bastardo in questione è tuttora vivo e vegeto sul pc del cliente, in attesa di una formattazione che non ho particolarmente intenzione di fare.

Se qualcuno ha suggerimenti, dica pure; tenete conto che su quel pc ci sono già stato diverse ore, e normalmente me la cavo in pochi minuti.