One other clue on this problem: I have two machines at home. I use both to connect to corporate network via Juniper SSL VPN. One always works, has no problem with dscachecleaner. This machine runs Internet Explorer 6.0.2900. The machine with the dscachecleaner problem runs Internet Explorer 7.0.5730.11. Maybe my version of Internet Explorer 6.0 is old enough to have escaped the problem.
This issue took months and months for JTAC to figure out. The issue is within the Index.dat file and affects IE 6, 7 and 8. We are a large company that is still using IE6 so we were not able to confirm the issue in IE7 and IE8. Clearing out the temp internet files in IE7 and IE8 should fix the issue...but only temporarily (according to JTAC). In IE6 it requires a 3rd party tool. Of course, until you upgrade to 6.5R4, it is possible and in many cases very likely to return. We reimaged PC's and rebuild user profiles only to have the same issue return after a day in some cases, a week or 2 in others and in a few cases never.
The fix did not make the cut off date to be included in the latest 6.4 update so right now it is only included in the 6.5R4 code.