Have you done a search on the machine for iexplore.exe? Start, Search, Files and Folders...search on the hard drive.
Do you have ANY disks that came with the computer?
We have run into what I was afraid we were going to run into on a totally non-updated and extremely infected machine...that is the probably damage of much needed files.
But as it stands now, without these disks you couldn't even do a reformat if you wanted because you need those disks.
Give me all the info on the computer...make, model etc. And keep looking for those disks. You DO need them