Woolybit, do you have a credit or debit card? I think Paypal even offers them now?
I'm pretty new to all this but also got sick of high aussie fees. The best way I've found is to join Liqpay, and then you can send funds from your credit card to BTC-e.com (an exchange like Mt Gox). The only fees you deal with are 1% when you deposit the funds into BTC-e, and a flat 0.01 btc fee to withdraw your coins out of the exchange. Oh and I think it's 0.02% fee on every trade on btc-e (aka when you actually purchase the coins on the exchange)
A bonus is that you get to buy your btc on a proper exchange when the time is just right. I've only deposited money this way twice, but it all went ok. Be warned, expect the whole process to take around 24 hours for each deposit, until you get fully verified at liqpay, & then the process is supposedly instant. (I'm still waiting on their verification snail-mail)