This better be the last post in the series, but it appears everything has been resolved.
When the system administrator finally responded, he included two sample traceroutes showing the problem had been resolved and explaining that there had been several abusive hosts flooding the network segment my server is on, which he had removed.
I guess this is the kind of risk you take when you go with a hosting company, but it’s so much cheaper than hosting things yourself, it’s really the only option.
Oh well, let me know if you have any further speed issues, I’m going to finally hit the sack now that I don’t have something to wait on… G’nite!