I run an OSC store here http://www.justgolf.com.au/ and have been having issues as well. There is an Australian shipping module which you can easily install but it adds up the shipping when it doesn't need to. I.e. if a customer buys 2 items it will charge them twice for shipping when with most of my products I can combine shipping.
Currently I'm just adding the shipping into the total price and advertising it as free shipping. I've also found this which may be of use http://www.oscommerce.com/community/contributions,4129