I had the very same problem when I started hosting ~10 years ago (I was mostly a hack designer back then) and it racked my brain for 3 weeks...

Same situation. A local, reluctant ISP had us in their folds and I am fairly sure they didn't know how to diagnose their own problem either.

Back then, we didn't have a lot of information or the resources that we have today. When I say "we" I mean the general public. Google was not even a search option then and reading newsgroups was a tedious process.

That's why older hosts were able to get away with charging $24.95 for 100 megs of space.

Ahhh, the good ole days. LOL!