Windows Update

Normalmente lo que sucede es que estos Fake genaran valores en las llaves de registro de windows, para limpiar tu registro se me ocurre, que le pases el CCleaner, este programa elimina los valores que no tienen su contraparte (el programa que los creo), me imagino que para eliminar el Fake usaste el AntiMalabytes, en tal caso recordaras tendrías ingresar en modo seguro a windows y ejecutar el programa, haríamos lo mismo con el ccleaner, una vez limpio el registro reinicias tu pc y listo!, debe quedar. ¿Si no funciona solo postea y probamos con otra cosa OK?
Bajate el CCleaner!

Muchas gracias por tu rápida respuesta, erickahr.
He hecho lo que me has aconsejado, y ésta es la situación:
Los accesos directos a Windows Update (http://windowsupdate.microsoft.com/) siguen sin funcionar (siempre aparece el mensaje "Internet Explorer no puede mostrar la página web", sin ningún número de error).
Sin embargo, ha sucedido algo curioso, al menos para mí, que soy una novata en estos temas:
Si accedo a través del "Centro de ayuda y soporte técnico del sistema", es decir, haciendo clic en "Inicio" - "Ayuda y soporte técnico" - "Mantenga actualizado su equipo con Windows Update", sí aparece la página de bienvenida de Windows Update, con sus dos botones ("Rápida" y "Personalizada"). Incluso (y esto me ha sorprendido aún más) al pulsar los botones, la operación ha concluido satisfactoriamente, es decir, me ha mostrado la página de los resultados con las actualizaciones disponibles...
Pero el proceso se ha desarrollado con normalidad una sola vez. Cuando lo he intentado repetir (en varias ocasiones), todas las veces ha vuelto a falllar.
En estos últimos casos, es decir, intentando acceder desde "Centro de ayuda y soporte técnico", sí aparece un número de error (0x80072EFE). Lo hace durante sólo unas décimas de segundo (tengo que hacer una captura rápida de pantalla para poder leerlo después) y le sigue inmediatamente el mensaje típico: "No se puede mostrar la página".
Y en ésas estamos, una y otra vez...
Saludos.

OK, ese error que me comentas se refiere a un acceso que no se ha podido realizar... intenta poner tu firewall con la configuración por defecto o bien desactivarlo (temporalmente ) y lo mismo con tu antivisrus... con toda tu seguridad desactivada, intenta hacerlo... si funciona es que tu antivirus y/o el firewall están interfiriendo... me indicas que antivirus tienes y te comento como podemos configurarlo para que te proteja y no te de líos con la actualizaciones.
Slu2

Hola erickahr. Gracias por tu interés.
En realidad, desactivar todos los sistemas de seguridad (firewall, antivirus, antispyware...) es lo primero que hice. Incluso llegué a desinstalarlos y probar así, pero fue inútil. Seguía sin funcionar.
También he chequeado el equipo en estos días con varias herramientas online en busca de malware y, aunque se han detectado "cosas" (de bajo nivel de peligrosidad), su eliminación no ha solucionado nada.
Me da a mí que esto se encamina al formateado, ¿no te parece?