Data Retention Law Passes the Oz Senate: Which VPN Service Do I Recommend Now?
PIA (https://www.privateinternetaccess.com) are reliable, have a new AU node and are well-regarded on WP forums (http://forums.whirlpool.net.au/forum/87).
Also check this list for Oz VPNs: http://www.vpnanalysis.com/5-best-vpns-for-australia/
ipredator.se founders truly care about privacy. They are running a TOR exit node with the highest bandwidth capacity.
Your latency won't be great, but d/u speeds are fine.