Si se trata solo de la infección que mencionas, no lo veo tan grave como para formatear, pero concuerdo con nabucco en lo de las páginas inapropiadas y lo de dejar de usar Internet Explorer.
Lo que puedes hacer es desinstalar esos programas en Modo a Prueba de Fallos y luego seguir
estos pasos.
Ya nos contarás como te fue.
Saludos