Spyware Attack!!!

Hi people!

I installed XP professional 2002 recently. And off late im experiencing wierd happenings with my system. List of 'em:

1) The loading page of my IE has this message:
Detected SPYware! System error #384
_________________________________________________________________
Your IP address is XX.XX.XXX.X. Using this address a remote computer has gained anaccess to your computer and probably is collecting the information about the sites you've visited and the files contained in the folder Temporary Internet Files. Attention! Ask for help or install the software for deleting secret information about the sites you visited.

_________________________________________________________________
Your computer is full of evidences!


ISP of transmission: 134
Your IP address: XX.XX.XXX.X
They know you're using: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; DigExt)
Your computer is: Windows XP
Risk status for further investigation: VERY HIGH RISK

To protect from the Spyware - click here
To prevent information transmission - click here
To delete the history of your activity, click here

2) I tried to look for info on this problem and came to know about HijackThis!. I downloaded that and when I double click the installer, it does not load up. Looks like the Spy is getting rid of it.

3) I downloaded Service pack 4 for XP and the same thing happened. It starts extracting files and vanishes in the process. Same case of the Spy playing evil.

4) In my command promt, i cant run "regedit", or any applications related to antivirus. Calculator, IE and others work normally from the command promt.

5) Last but not the least, any antivirus I load is not working.

The main problem is that i know that there is a spyware and im trying to remove it, the applications vanishes....

Any help will be higly apprciated.

Eagerly Waiting...

Guru Charan