CrystalTech were very good and only had one issue with a dedicated server in 5 years when a network cable came loose which was fixed after a quick phone call.
WebCentral has a horrific control panel, only one possibly worse is the cutdown Telstra Business version.
Currently using VentraIP/Zuver for a handful of VPS servers and they are always friendly and responsive.
I guess you have to pick your poison, a company that might not be so great but has been around, or someone that is great but fleeting. Although that is starting to change now with Linode, Rackspace, and others.
Plus I know of a smaller company that's intending to move in here. Hope that goes well...
The other consideration is the legals. Moving the server to Germany not only puts your data under EU/German jurisdiction in addition to AU, the new privacy laws to take effect next year will mean disclosing to your clients and they to their clients that personal data is stored outside of Australia.
Started with one place I can't remember - started with S. It was cheap and allowed multiple small sites to run off one account. Eventually turned to crap and so we bailed.
WebCentral - gave up on their silly control panel.
Used a place in NSW or Vic that started off OK, then was acquired (BlueCentral, I think?) and turned into a bit of a rude disaster. Abandoned that. Had a site break on Friday of a long weekend, so no support until Tuesday...
Had 60+ clients with CrystalTech who were polite and had great service. They were bought by NewTek and started overloading shared servers and tech support went from efficient and polite to slow and especially dim-witted. Bought again by SBA and things got worse. We've gradually shifted dozens of sites to accounts at Linode and that's been a great move for us.