In the meantime, I did what I promised Adrian Klaver I would do and I added the AD servers to the /etc/hosts file. That had an immediate and dramatic effect on the performance. That confirms (at least to me) that DNS resolution was playing a large part in the slowdown. I'm going to experiment with running a local DNS caching server to see if that will give the same effect.
I had this problem at one site, and with the same solution. As best as I could tell, Windows was not using DNS as the main way of resolving hostnames. (People assure me that NetBIOS and WINS are almost completely dead, but WireShark tells a different tail--I don't recall the exact name, but it was certainly something other than DNS). So the fact that AD's built in DNS sucks was not a problem for Windows users, which means there was no impetus on the Windows admin to fix it. And the delay on resolution was always 5 seconds plus a very small handful of milliseconds. So it was clearly some kind of designed throttling or timeout, there is no way random congestion could get you so close to 5.00 every time.
If we had greater depth of talent on the Windows side, surely we could have fixed the DNS issue. But with greater of talent, we would have been using Kerberos in the first place, like Stephen wants us to.