Al desinstalarlo asegurate que sea del todo. Bajate el CCleaner y ejecuta el limpiador varias veces y luego la herramienta de limpieza del registro (haciendo backup).

Descargate el JRE (Java Runtime Environment) desde aquí:

Descargar el software de Java de Sun Microsystems

Es el último... de otra manera, si estás interesado en tener todo el kit de desarrollo incluyendo compilador, blablabla... El ultimo JDK (Java Development Kit) está en:

Descarga gratuita del software de Java - Sun Microsystems

Si sigue sin funcionar puede ser un bug de tu SO, que es probable por lo del error en esa referencia a la memoria. Creo que hay un patch para eso, pero no recuerdo bien.