Hmm. dobrej popis. Pravděpodobně sis zavšivil PC.
Zkus SuperAntiSpyware dle tohoto návodu. Pak můžeš pro jistotu i AdwCleaner a MBAM (jak jsi psal, oba programy používáš).
Teď jsem si všiml, že tam máš napsanej i CCleaner - pokud ho používáš i na čištění registrů, tak Tě stejně nová instalace Windows nemine...