Comment by pveugen

Mapbox offers maps, geocoding, and directions, with solid coverage in Australia.

https://www.mapbox.com/geocoding/

Happy to answer any questions.

Disclaimer: I work at Mapbox.