It's pretty hard to find proxies in Australia. I'm a proxy provider and I have nothing down hear and the reason is pretty simple - the cost of hosting and bandwidth is crippling. For a 2Mb unlimited Tier 1 Internet service, you're looking at $800 or more per month, and the server hosting will be another $200 or so at best. At these costs I'd have to be selling the proxies at $20/month each to make money.
On top of this, we have some of the toughest online/Internet laws around, and I don't really want to get a please explain from the Fed. police about what my users have been doing.
Bottom line is that there are no private proxy providers in Australia, and that is not likely to change any time soon.