RegVac will remove the Java entries that have URLs in them. You may be able to use the Software Cleaner to remove other entries.
No, I do not recommend their suggestion. I don't see the advantage of using Sun over Microsoft. Malware does not come from Microsoft Java, it comes from opening email attachments and going to questionable websites. You control those two things and you will control the malware.