Non c'è bisogno di formattare, basta avere delle utility che ti dicono cosa cambia e cosa no nel registry.

calbe è incappato nel classico caso da Windows pazzo (da ivan il pazzo del film ottobre rosso )
windows ti si rigira contro, perché ogni volta che lo accendi legge nel registry le impostazioni di sistema.
Siccome spesso i disinstallatori non puliscono bene il sistema, ovvero non puliscono il registry, ma lo sovrascrivono, magari in posizioni diverse.

I rimedi sono molteplici, dalle utility che puliscono il registry ai sistemi di installazione/disinstallazione che tracciano tutto ciò che succede quando installi un programma.
Io sul 98 uso l'ottimo ezclean, uno shareware che ho registrato, anche perché non riuscirei mai a farne a meno.