Here's a list of Australian VPS providers. <a href="http://www.vpsau.com/" rel="nofollow">http://www.vpsau.com/</a><p>Unfortunately they don't all provide self service and some even have a setup fee!<p>The amount of traffic you get varies. For $40/month I've seen 5GB up to 60GB traffic on a 256MB VPS. I'm one of the people shocked by the true impact of choosing cheaper overseas hosting. I'm also running 12 VPS's at home on a DSL connection and they're super fast for Aussie users.
As an Australian I can confirm that the AUS to US latency (or AUS to anywhere really) does indeed suck. I REALLY notice the difference when I on an Aussie site.<p>However hosting over in the US is a lot cheaper than it is to buy locally. Still, I'd urge application developers to buy hosting in the country of your target market.