What JRE you do have installed and working? If it is one of the 1.6 versions, you might as well just use MsiX.EXE, a fantastic command-line tool, able to extract files from .msi, .msm and .msp installation files to extract the .msi contents and then put them in place, over the old ones... it's labor intensive, but it might work.
I have 6u7 installed. I've also tried uninstalling this first, but it doesn't help.
MsiX isn't doing too well for me, it extracts about 10 files, some only partially renamed to their final names. AFAIK, MsiX uses the API's of the installed MSI stuff on the system. When that's not working properly, neither does MsiX. At least that's what I've concluded just now. BTW, the MSI stuff on my system does work properly for other MSI files that I've previously installed, it's only this Java stuff that it has issues with.
I wonder what version of 'msiexec.exe' others have, and what KernelEx settings it has? Mine is version 2.0.2600.2 (MD5 = 53223ff3012db1ac5a35cae4720bdd46). I get a different error message depending on what KernelEx compatibility settings I use, but it seems to bomb out at around the same point either way.
Speaking of MD5 hashes, these are the hashes of the files I get after attempting to run the 6u39 installer :
Data1.cab = 4ce133f19d40787a5548a6afcf15541e
jre1.6.0_39.msi = 606aac2b60cf3e37baebd8a744cf300c
Perhaps someone can confirm these are OK (else it would mean the installer extraction process is the problem).
Try: Skip CheckPendingFileRenameOperations action with SuperOrca or Orca.
I tried this just now (deleted 3 or 4 occurrences). Unfortunately, it didn't help.
It's frustrating, but I don't seem to be the only one having problems with this Java stuff.
Anyway, there's now a new version of this thing - that also won't install for me : 6u41.