Malware or something else?

I'm running a quite recently installed Win XP Pro with Norton AV as my main protection and Mozilla Firefox as browser, but a few days ago, I found I cannot do searches with Google or any other search engine, and some random sites cannot be accessed any longer. They simply stand waiting and nothing happens.
This is what I have done:

1. Someone mentioned somewhere it could be a DNS problem, so I flushed it.

2. I have run a complete scan with a fresh (and legal) copy of NAV. Apart from an occasional tracking cookie, nothing found.

3. I have followed the entire guide stickied on this forum and HJT did find some stuff. Two itemsd couldn't be removed however.

THat is what I have done, and short of another installation of Windows, I have no idea what might be wrong.

Any help appreciated.

 

Post the logs that were produced during the running of the Read Me. Without them we have no idea what is happening with the system.

 

Strange - I can't attach files? However, I have them copied here:

The log file:

Logfile of Trend Micro HijackThis v2.0.2
Scan saved at 01:07:21, on 2008-07-13
Platform: Windows XP (WinNT 5.01.2600)
MSIE: Internet Explorer v6.00 (6.00.2600.0000)
Boot mode: Normal

Edit by chaslang: Inline HJT log and Startup List log removed. READ & RUN ME sticky not followed.

 

Ah ok, sorry I missed.

I can't download the CCleaner, Spybot S&D, Malwarebytes and Superantispyware - it appears those are some of the places I can no longer go.

True, I removed some stuff from the system, which according to the sysinfo site were malware - I left a couple which I couldn't find in the lists however. I run a pretty compact system otherwise.

 

This is so very strange - now, without having done anything more than previously stated, I suddenly can use Google again... I will still download all the programs however and run a check when I have time.