JJ, I have encountered a similar situation myself on only 1 occasion. It was with an XP machine. Though it has been sometime back, as I recall it, I had at that point felt confident in having ruled out malware as the culprit. Which brings me to this point you mention about a "strange incoming gateway". I believe that until I had that issue resolved it would be my primary focus. You may very well find that the ATE (Answer To Everything) procedure would be the most prudent. i.e. Wipe clean, format and reinstall. Rootkits are often not easily detected and cleaned. Further, I have my own doubts as to whether or not the system can ever be trusted to be completely free of them once they are compromised.
Still, I will provide the solution that worked in the above example for you to try. This will involve forcing a reinstallation of the TCP/IP stack within Windows. Proceed at your own risk however.
First open regedit
Navigate to: hklm\system\currentcontrolset\services
In there you should find 2 keys named Winsock and Winsock2
Before going any further, export those 2 keys!!!
After exporting them, delete both keys completely
Next proceed to your %windir%\inf folder
Search for nettcpip.inf there
Open it in notepad and look for the [MS_TCPIP.PrimaryInstall] section
There is a setting "Characteristics = 0xa0"
This is responsible for the fact that you can't uninstall TCP/IP in Windows XP
To reinstall it, we first need to change that fact
So change 0xa0 to 0x80
In the end you should have Characteristics = 0x80 in the nettcpip.inf file.
Save the file. It may be necessary to change the file properties from Read Only first.
Also be sure that you save it as nettcpip.inf and NOT nettcpip.inf.txt.
Thank MS for their continued policy of dumbing-down their users for this one.
Be sure that your Windows Explorer property sheet does not have a tick in the "Hide Extensions Of Known File Types" setting.
Next go to Control Panel -> Network Connections
Open the properties of the "Local Area Connection"
On the General-tab click on "Install" -> Protocol -> add
In the next window select "Have Disk"
Point it to c:\windows\inf
Select internet protocol (tcp/ip) from the list
Thats it and good luck.