Aussie Post will do a Western Union money order, but instead of costing $12 for a cheque, it costs around $28. They can do them online for you, but they take a "small" surcharge which is double the cost of going to a bank and having an International Cheque drawn. It takes the same amount of time for the Bank to write the cheque and it is cheaper.

WU is not an option for me anymore - even on big orders.