i second siredesigns. New joomla! 1.5 series + new VM 1 .1 series is a combo winner for a shopping cart system.
really powerful and complete. And the learning curve is not too hardcore.
I’ve been using Drupal and Ubercart for quite a while, but we are working on switching over to Magento (integrated into Drupal). Magento looks fantastic.
Played around with both oscommerce and zen cart as both are open source and they seemed to have good modules for australian shopping, credit card, and easily be integrated with Australia post with overseas assistance as well.