Revo can do a deep scan and remove associated files and keys. If it isn’t able to detect that Java was installed, try creating a few fake registry entries in the tree used for ‘add or remove programs’
In the past I’ve exported a few Java registry keys from a PC with a working Java install and imported them onto a PC with similar problems to you. Once you give it a whiff; Revo does a pretty decent job.