Java Error al abrir la clave de registro

Recibo este error cuando intento hacer algo con Java en el símbolo del sistema:

Error opening registry key 'Software\JavaSoft\Java Runtime Environment.3'
Error: could not find Java.dll
Error: could not find Java 2 Runtime Environment

Hace unos días eliminé los directorios y el registro de Java. Reinicié la computadora y Java todavía funcionaba bien, luego lo reinicié nuevamente hoy y ahora aparece este error. He intentado desinstalar y reinstalar pero eso no parece funcionar. Tengo el último Java JRE instalado y la ruta establecida en las variables de entorno. ¿Alguien tiene alguna idea de cómo solucionar esto?