Sounds to me like an IRC bot that is running rampant. If none of the above works for you. Go to the sysinternals site and download TCPView. Be sure you're an admin when you run it.

Look for the rouge explorer.exe process and right click it to see where it's spawning from. Go there and delete the file once you kill the process.

Now, this file is called from the registry usually from here:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Run

Go there and look for a key that fires this malware app. It will reference explorer.exe wherever you deleted it from.

This *should* be enough to kill it, however, it has been seen where these things anchor deeper than this.

--TH13