Servers cannot see internet gateway though their configuration is the same to another which can

I have 2 switches at the Data Centre - one is connected to the internet, and one for the internal private network.

All servers have one NIC into the internet switch and one to the private one. All servers are ok, except three: Those three servers are visible just fine in the internal network but are unable to ping the internet gateway or be visible from the internet. They have what seems to be the exact same setup in the interfaces and resolve.conf files (with of course different public IP addresses to them but the rest are the same). 'route' shows the same output on those 3 as in another server which works perfectly, yet they cannot access the internet and when I ping the configured gateay from those 3 ping responds that the host is unreachable. When route runs on these 3 machines it pauses a few secons before it displays the gateway (probably as its unreachable).

The servers are all Debian 6. Iptables has no chains/rules.

I've been standing in the Data Centre for the past few hours trying to figure this out. Any help highly appreciated