sky-night, you were close: The routing table on that server is misconfigured.

I've seen this issue before on client systems and even at work but have yet to see it on my domain until today.
"The default gateway is missing on a computer that is running Windows Server 2008 or Windows Vista after the computer restarts if the default gateway is set by using the Netsh command";EN-US;973243
Although this fix applies to Server 2008 and not Server 2008R2, a Google search turned up many an IT folk having this problem with 2k8R2. Anyway, I manually cleared the IP settings on the server and specified the settings again, rebooted, started working.