I had been recommended this group http://www.transdirect.com.au/
from somewhere on a bike blog. I was looking at around $100 ADL - MEL. I think I'd probably check some of the bigger outfits as well.
(Not TNT - they took 5 days to get 4 cases from St. Kilda Rd to Mt Eliza for me a couple of years ago. It would have been quicker to get a trolley and walk them down myself. Hopeless.)
Advantages: door to door service - no dragging a bike box around the place.
It's worth adding up all your weights and mixing your bags accordingly, between carry-on, sports and road freight. All the best...
On a recent tour round Nth NSW I found Virgin Blue people to be very helpful re leaving my box at Ballina airport and so on.