Meine Vorredner haben schon alles wesentliche zu Linux gesagt, aber warum bereinigst Du den PC nicht einfach "richtig"? Solange der Verdacht auf Malware besteht, ist auch eine Linux-Distribution im Zweifel nicht sicher genug (Java gibt es z.B. unter beiden Plattformen). Ferner leistet man mit einem nicht sauberen Rechner nur der Verbreitung von diesem Krabbelzeug Vorschub.
0) Alle wichtigen Daten sicher --> idealerweise auf eine externe Festplatte oder ein optisches Medium. Diese kann man vorab mit einer Linux Live-CD und CalmAV schon mal überprüfen. Außerdem neue Zugangsdaten für den Internet-Provider und v.a. das Online-Banking beantragen.
1) Festplatte mehrfach in unterschiedlichen Dateiformaten formatieren --> am besten geht das mit
GParted. Am Ende HDD in NTFS formatieren
2) Windows neuinstallieren, währenddessen auf einem sauberen Rechner alle Win-Updates (z.B. mit
C´t Offline Update), aktuelleste Treiber sowie aktuellen Viren- (z.B.
GDATA-Trial) und Spyware (z.B.
Spybot)-Scanner und aktuelle Internetsoftware herunterladen und auf CD/DVD-Brennen
3) Nach Installation alle Updates, Scanner und Treiber einspielen, als letztes Netzwerktreiber (bei DSL) installieren. Den Rechner jetzt auf Viren/Malware untersuchen. Zusätzlich würde ich einen oder zwei Online-Scanner (meine Favouriten sind
TrendMicro und
Panda) hinzuziehen.
4) Jetzt die gesicherten Daten auf die gleiche Weise behandeln und - wenn sie sauber sind - wieder zurück spielen. Damit hast Du eine 99,5% Sicherheit hergestellt - mehr hast Du auf einem neuen PC ohne Daten auch nicht, denn ein Schadprogramm kann trotzdem jederzeit eindringen.
5) Zum Schluss würde ich wirklich alle Passwörter ändern und dem User ein Programm wie KeePass 2 zur Verfügung stellen das diese speichert und ihn außerdem zwingt sie regelmäßig zu ändern (niemand kann sich 10 oder mehr Zufallspasswörter merken und schon garnicht wenn die monatlich gewechselt werden

).
Grüße