hay herramientas, que los mimismas compañias hacen para borrar por completo la aplicacion o el programa, normalmente suelen llamarse (removal tools) algo asi, deja busco aver que en cuentro, por que la mayoria de los programas lo tienen, como, norton, karpesky, nero, avg, tambien tienes que estar seguro que version vas ainstalar, 32bits o 64 bits, la version de 64bits puedes instalar los dos programas 32 y 64, (solo la de 64).
ok deja busco aver que encuentro.
encontre uno tratalo esta en ingle.
http://www.mediafire.com/download.php?l510vdavbd2cipw

Busca en las variables de entorno de tu sistema el JAVA_HOME o JRE_HOME, quizás ahí encuentres la ruta donde se instaló quizás sin que tu te dieras cuenta el JRE de Java

Usa el JavaRa http://javara.softonic.com/ es el limpiador para todas las instalaciones de java, despues de ejecutarlo intenta instalar de nuevo la version de java nueva.