You should try PPC, search for forums and blogs in Australia, as well as local business listing, web 2.0 and blog comments on Australian websites.
Not to State the obvious, but have you considered purchasing traffic?
Not presumably, they stated it in their OP (emphasis mine)
I cannot think of a good reason ever to “purchase” traffic, and those reasons I can think of all would violate the terms and conditions of various search engines.
If you want traffic from specific location like australia, then firstly you have to find the websites which has Australian traffic for that you have to check traffic of a website on Alexa ranking. Make a submission on the website which have mostly traffic from Australia.
It’s been two months since we last saw the OP, so there seems little point in continuing the discussion.
Thanks to those who contributed.