Fast internet is definitely possible in Australia, although right now, you might need to move to get it (alas). It's also not yet cheap (but we can partially expense internet, and you can also write it off for tax).
But I'm lucky, and I get that. We play the broadband lotto, and it's not easy to win. If I move I no doubt will be back in the ADSL2 world hoping I'm close to the exchange.
I'm holding my breath for when the NBN finally rolls through my area. Even 25Mbps would be acceptable at this point.
I had a chuckle today when I saw a restaurant in the Perth CBD was using a Vividwireless 4G modem. I would have thought the middle of the city at least would have a decent wired connection.
Both get 100 down, but Telstra Fibre only offers 5 up. The NBN on the other hand has 100/100 sync available if you want it.