Anche a me è capitata una cosa del genere. Nel mio caso si trattava di una specie di virus chiamato "downloader.istbar" che nn viene rilevato dagli anti-spyware ma solo da un antivirus.
Nel tuo caso si trattava di una variante(istbar) del TrojanDownloader ecco perchè era rilevato dall'av e non dai programmi antispy. Se le chiavi di registro al riavvio venivano ricreate significa che non effettuavi una corretta rimozione, la quale va fatta da modalità provvisoria, disabilitando anche ripristino configurazione su sistemi Windows ME ed XP per poi riattivarlo a fine eliminazione.