This is driving me crazy.

I have a virtualized W2K8 server running RRAS. Every other computer or server on the network can access the internet through the NAT except one.

On one server, it just won't work. I can ping the ip address of the NAT gateway just fine, and everything else works. (SMB, etc) DNS, which is hosted by the same server, also works just fine.

I have even reinstalled the OS on the problem server and it still doesn't work.

Recap of the steps I tried:

1. There are 3 network cards in the server, I tried every one and different switch ports. Not a hardware problem.
2. Reinstalled W2K8 R2 on server with the problem, didn't help.
3. Tried the IP of the internet gateway directly - this did work (!). But I need NAT to work.
4. All firewalls are disabled.
5. Removed computer from domain, deleted computer membership in Active Directory Users and Computers and added it back.
6. Disabled all other network adapters and set a static ip and specified the gateway ip manually.

When I tracert a public IP, the first hop (or any other hop) comes up as:

C:\>tracert www.google.com

Tracing route to www.l.google.com [209.85.225.106]
over a maximum of 30 hops:

  1     *        *        *     Request timed out.
  2     *        *        *     Request timed out.

From a different computer, on which NAT works, the first hop comes up as:

tracert www.google.com

Tracing route to www.l.google.com [209.85.225.105]
over a maximum of 30 hops:

  1    <1 ms     *       <1 ms  xxxx [10.5.1.1]

This is the most bizarre problem I ever came across, and I realize that it's a long shot asking it here given all the details, but I'm pulling my hair out. Maybe someone has an idea...