It's getting better: http://www.rackspace.com.au/cloud-servers/pricing

Plus I know of a smaller company that's intending to move in here. Hope that goes well...

If you happen to be doing Rails development, it may be worth checking out Ninefold: http://ninefold.com/pricing [no affiliation of mine]

If you don't mind renting a server in germany, checkout Railscloud (https://railscloud.de/)

Germany has good value but there are a number of issues with hosting overseas. Latency is one - in Australia one of the cheapest hosting companies is based in Perth but the latency is double that of Melbourne, Sydney or Brisbane.

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.