If you looked at the log (open the spoiler), CrazyCracka420, you'll see that the routers in question were responding at the previous and the next attempts.
So far, for the half an hour i ran traceroute, i was unable to reach the server one time for a period shorter than 1 minute. That's consistent with what i've been seeing at home. I'll go home now and leave traceroute running for an evening. That should give us the data we need.
It would be really nice if a couple of you guys did the same. More results = more leverage to slap the hosting company with.