Na verdade, pensando duas vezes, em vez de fazer a reinstalação, continuei pesquisando mais no registro. Eu apenas procurei por 'java' e deletei todas as entradas que julguei relevantes para as entradas de tempo de execução do java (portanto, não o javascript, msjava, javavm, etc), e funcionou!
Eu tenho o java runtime 7 instalado agora, funciona como um encanto.
Então, se alguém mais se deparar com isso, pode valer a pena tentar cavar o registro manualmente!