I have a project on the cards for an Australian company who needs a recommendation for a good Australian payment gateway and payment processor. They do not have one at the moment and as I am UK based I don't know who would be the best to recommend.
I have done a little research, mainly into compatibility with Drupal Commerce but I would be very interested to hear if there are any Australians on gdo who have setup a Commerce based site with a local PSP.
The ones I have looked at are:
Merchant Warrior - http://www.merchantwarrior.com/ (has module at http://dox.merchantwarrior.com/)
E-Way - http://www.eway.com.au/ (possible module at http://drupal.org/project/commerce_eway)
Securepay - http://www.securepay.com.au/
Camtech - http://www.camtech.com.au/
As far as I can see only Merchant Warrior and E-Way have a Drupal Commerce gateway module.
I assume that the process is similar to the setup here in the UK, in that the bank account receiving the money will need to be 'merchant enabled', and that the client will need to complete various lengthy application forms with their bank.

Comments
Why wouldn't VirtualMerchant
Why wouldn't VirtualMerchant or CyberSource work? Are you concerned about dynamic currency conversion or gateway latency?
eWay
eWay seem to have a good rep.