I use
http://www.namescout.com/dot_au.asp
There was one place I found cheaper for around 56, but I preferred to go with a company that I was familiar with than to save 4 dollars.
Oh yeah the $59.99 at namescout is for two years registration, so about 30 aussie bucks a year which I think is quite cheap.