Often places will screw up their reverse records. You can tell you've got screwed up reverse records because if you run something like netstat -a and it takes a really long time to run and you get back a bunch of IP addresses in the rfc1918 address space. Not having reverse records in this space by itself isn't really a problem, but it is a problem if your DNS people forward their DNS requests to the providers or to a broken DNS server.
A quick way to verify if it is a DNS issue is to log onto the system and lookup an IP of someone connected to the system (look at netstat -a and look for established connections) and then run
nslookup a.b.c.d (or whatever the IP of that host is)
if you've got an older system, you may need to type
nslookup d.c.b.a.in-addr.arpa.
In either case, the result may be something like "can't find that address" but the answer needs to come back quickly. DNS timeouts can be on the order of seconds, and if you have 3 DNS servers in your resolv.conf, your server is going to try each one before it gives up. This can easily add up to a really annoying amount of time.
A quick way to illustrate the problem to your boss is to run netstat -an and then run netstat -a and then say "if our DNS was working properly, these would both run in almost exactly the same amount of time.
If it is a reverse-record issue, you can probably "fix" the problem by turning off reverse lookups in your applications. In this situation, it may be easier than getting another group involved.
There is also the remote possibility that there is a duplex mismatch between your servers and their switches. That can be tested by looking at the output of (windows) netstat -e or (unix) netstat -i. You're looking for "errors" or "collisions". If you see "collisions" then your end is mis-configured; it is half duplex and should be full duplex. If you see "errors" the switch end is half duplex and you're full duplex. Both counters should be zero, or at least small and not increasing. These problems can be really hard to track down because the link will work pretty well if it is unloaded and totally fall apart when there is lots of traffic.