I'd give all the responses here a try first. But I wanted to just throw in what I do, just in case these do not work for you.
I've tried to solve the same problem you're having before, and in the end, what I decided on doing is to have only one JRE installed on my system at a given time. I do have about 10 different JDKs (1.3 through 1.6, and from various vendors - Sun, Oracle, IBM), since I do need it for development, but only one standalone JRE.
This has worked for me on my Windows 2000 + IE 6 computer at home, as well as my Windows XP + Multiple IE computer at work.