Author's note: This answer was written to address installations of Java, major versions 6 and 7. It may or may not work with versions of java that are newer or older, but it probably won't hurt to try. If you follow these instructions for a major version not listed, please comment whether you were successful or not.
Read all of the directions twice. This solution details a manual uninstall of java by modifying the windows registry. If you do not follow the directions, you can cause permanent damage to your windows installation and will need serious firepower to get it working correctly again. If you do not understand the risks, ask someone for help.
If you have any registry cleaners, get rid of them. This is probably their fault. I've never met one I liked and wouldn't let one touch my registry with a 10 foot read only pole.
If you're using a laptop, connect to a charger. If you have children, make them walk the dog. Find a quiet secluded place and hole yourself up in it with zero distractions for about 15 minutes.
Make a backup of the registry key "\HKEY_LOCAL_MACHINE\SOFTWARE\JavaSoft", save it somewhere safe.
Delete exactly the following and only exactly the following registry key and all of its subkeys: "\HKEY_LOCAL_MACHINE\SOFTWARE\JavaSoft". After you are done with this step, java is dead. Do not try to run any java programs at this stage, it almost certainly won't work.
Open "C:\Program Files" (and, if you're on a 64 bit machine, "C:\Program Files (x86)"). If you see folders called Java, rename them to "Java_". If you installed java to a nonstandard location, navigate to it and add an underscore to its name.
Download and install the latest version. The installation should complete with no issues. It should also overwrite any leftover chunks of the old installation that are left.
(optional) Uninstall java again. The uninstallation should go smoothly and it should properly dispose of any leftover resources installed by the broken installation. Reinstall when the uninstall is complete. Since you are installing the same version you just removed, this probably isn't necessary.
Final note: I have performed this surgery many times on other people's computers using teamviewer, and it has never gone wrong. In the social circles where I hang out, we call it a javaectomy. For reference, I hang out on IRC and help people with issues with minecraft. We think we have seen every possible java issue. This one is fairly common and caused by some combination of many concurrent java versions, registry cleaners, and interrupted or failed updates. Once you are done and have verified that the reinstallation has gone smoothly and without issues, you can remove your saved registry keys and delete the renamed java folders from "program files" and "program files (x86)" (remember to delete only the ones with an appended underscore, the one called Java was added by the reinstall and should be left as is.
Disaster recovery: In the unlikely event that something goes wrong, restore the renamed java folders and patch the registry keys with your backup to revert to the original (partially broken) state.