win cant find msconfig and searches are redirected

My searches in both Google and Yahoo are frequently, but not always, redirected. Sometimes I get a "Windows can't open this page. Click here to diagnose the problem" message. Usually when I "click here" or hit refresh it will take me to my search result. Then when I click one of the links it sometimes takes me to a "shop here" website, or sometimes it takes me to various "Your system could be infected so you better send us money" site. Sometimes it will redirect me every search all day, and sometimes it only does it a couple of times a day. I typically update and run MalwareBytes and Spybot every couple of weeks. I keep AVG Free running all the time and it updates daily. About a week ago MalwareBytes found and deleted some malware. A couple of days later I started having my problems with redirected searches. I don't know when msconfig went AWOL.

I went through and followed the "Read & Run Me First" guide which is when I discovered that msconfig is missing so I couldn't perform that step. All other steps were completed and neither malware nor viruses were detected. The requisite logs are attached.

I'm running XP SP3 and my browser is IE8.

Any help I can get to stop the redirection and to find msconfig will be greatly appreciated.

 

Thanks for the response TimW.

It looks like I left out a couple of things in my original post. It was late and I was seriously irritated. Sorry.

I saw that fix for msconfig in another thread and had already tried it to no avail. I tried it again just now and it still doesn't do the trick. I did get the success message.

If by "clean internet temp files" you mean "tools/internet options/delete" in IE, then yes. I do that every couple of days. If there's a more proper and complete way to delete them, then no...but I am willing to learn. I took a quick glance in Firefox but didn't see how to delete them from there. I also ran CCleaner as is recommended in the Read & Run Me section for what it's worth.

I'd never used Firefox so I downloaded and ran it without importing settings from IE. I still get a "Connection Interrupted" message and when I finally do get to my search results they usually get redirected. Again, though, it doesn't happen every time. I've noticed that once I finally do get to the search results that if I do the same search again later it will take me to the results without issue and those links don't get redirected (again, this is usually but not always the case).

I also forgot to include that when I boot the computer I get a message box titled "Data Execution Prevention - Microsoft Windows". In the box it says:
To help protect your computer Windows has closed this program:
Name: Application Layer Gateway Service
Publisher: MIcrosoft Corporation
Not sure if that's relevant.

On another note, I just "explored" my computer looking for a Temp Internet Files folder to delete files from and I noticed that under C:/Windows there are about 100 folders with names like "$hf_mig$" (under which there are about 75 folders with names like "KB873333"), and "$NTServicePackUninstallIDNMitigationAPIs$", and "$NTUninstallKB888795$". Most of them look like the latter. These folders show their Date Modified as anywhere from 2005 through April of 2009. I'm reasonably sure these folders weren't there last week and I'm dead certain they weren't there 2 months ago.

Thanks for the help and please let me know if there is anything else I should do.