So on those hosts which you connect to, can you resolve the IP addresses of these two servers? This is just a tangent but I've found that some sites are set up to try reverse DNS, and take a lot of time if it doesn't work. ident would be another thing to look for -- do you have an ident daemon running on one host, but not on the other?

You are saying you can ping by IP address from the OK host, but not from the broken one? That would rule out anything like this. But then you shouldn't be able to traceroute either ...?