Vírus de Propaganda no Navegador

Estou começando a trabalhar com manutenção, e atendi recentemente um cliente com este problema. Procurei por chaves de registros inválidas em execução e as removi, desabilitei a inicialização de programas desconhecidos, desabilitei as extenções desnecessárias que ativavam as propagandas, depois realizei um scanner com o avast e removi os vírus, depois passei o doctor web currelt e removi os adwares restantes. Após tudo isso , reiniciei a máquina e voltou ao normal. Algumas horas depois o cliente me retorna informa que o problema voltou, sem que ele tenha instalado nada. E agora? Tem como remover esses prováveis adware, sem ter que formatar? Estava pensando em usar o AVG rescue cd, que faz o scanner pela bios. O que acham? Tem outra alternativa fora esta?