Vá a Adicionar ou Remover Programas e desinstale todas as máquinas Java.
Reinicie o sistema e apague a pasta C:\Programas\Java.
Vá a este site e descarregue o Java Runtime Environment (JRE) 6 Update 7 (o 5.º item da listagem), clique no botão Download, seleccione a sua plataforma, seleccione o I agree..., clique Continue, descarregue o Windows Offline Installation, corra o instalador, reinicie o sistema e teste.
Boa sorte,
Zee