Based on what you have posted in all, it seems your reverse route from the server in Germany was completely stuffed. I previously had other bad EU routes on a 115.70.x IP, so I asked to be re-routed to a 220.233.x IP and that seems to have fixed it.
Anyway now that you've jumped ship to Internode, enjoy the extra consistency while you're at it.
Connection issues, drop outs or speed related faults for ADSL and ADSL2+ services
My main issue was definately not being able to play that one server, as much as I would like to have just said "hey ill host one in Aus" the mod owners are not into allowing this (its been asked by many) nor do I have the money needed to get decent hosting for a game server. Besides, there are other benefits to the churn, Ipv6 to learn and play with, FetchTV, are 2 off the top of my head.