I just got this reply from our GSP:

"I am not disputing that you are having an issue, though the fact remains that there are no problems on our end in the datacenter. It's possible that there is a network outside of our that you and your players are passing through that is having problems. Aside from moving the server to a different location, or reinstalling it, there is not much more that we can do."

Basically we must wait until someone between us and our GSP to fix the problem. Sorry, I wish I could do more.