I know you don't think that this is a DNS problem. I suggest that you go over your DNS with a fine tooth comb and if you don't see anything wrong with it... Get a second opinion.
We had this same problem and it turned out to be the reverse DNS lookup entries that were incorrect. The IP numbers were wrong. They were set for the old IP address range for the private network so the numbers were real close and we just plain ol' missed it. Troy E Bouchard Network Support MtIda.net
