Just a few random thoughts ...
Have you changed a NIC, or done anything else which might have confused the
arp tables on the router for that network, like moving the IP's from another
server? It's definitely clutching at straws, but try clearing the arp
tables on the router that handles internet traffic for that server. From
everything you've said, it sounds like a routing issue.
Do you just have the one NIC in that server? I've had similar sounding
problems when trying to use two NIC's in a BQ box ... I eventually gave up.
Is there any indication that packets are hitting the box from the Internet?
Like, does a 'netstat -an' show any connections from the outside world in
any state?
Can the outside world hit any other ports on the box, like SMTP?
And of course, check your default gateway setting. I'm sure you already
have, but check it again! See if you can 'lynx' or 'wget' from/to an
external site from the server.
-- hugh