Thanks for everyone's input on this problem. It turned out that they WAN folks added a throttle on the firewall between the spam filters and the DNS servers to limit queries to 100 per second. Any additional requests were just dropped, causing the IP stack to bog down.