Una volta disinstallata Java, hai cancellato la cartella del programma? Hai effettuato quindi un'accurata pulizia del registro con qualche apposita utilità? Quasi sempre, la disinstallazione di un programma ti lascia la cartella originale con un sacco di scorie dentro, e la successiva reinstallazione va a finire proprio lì e molte volte si "inquina" di nuovo, per non parlare delle voci di registro. La mia è solo un'ipotesi, ma vale la pena di tentare; ti ci vogliono pochi minuti.....
P.S. certo che se c'è di mezzo anche NAV, la situazione si aggrava.....