Well, days of troubleshooting later and we found a common network segment they all hit somewhere in Wisconsin, and the owner of that physical network found a bad piece of hardware on a telephone pole. I forget the details of what the hardware was or why it threw a fit with our site but not others... but the bigger point is that there are many layers in a network, so while software might be the problem... it also might not.
So my approach has always been that if it makes no sense for software to be causing an observed problem - investigate the other layers.