I'm in a similar situation to you since I'm working on a site that will be subscription based in Australia (for an international audience though). So far I haven't found anything decent for capturing and handling credit cards that work easily in Australia - maybe there's a (very small) market in there?
The current plan for my startup is to use a third party service like Spreedly connected to the payment gateway EWay (which is an Australian one) and then to an Australian bank (which I'm having most trouble with now).
Just a few words of warning though from what I've found so far.
There is http://pin.net.au where the amazing thing is you don't need an internet merchant account with a bank. They are in closed beta at the moment.
I know this question is old, but in case it helps anyone, I just moved to Australia and am evaluating payment processing solutions. I can't vouch for them, having not integrated yet, but a trusted business colleague here says that Payment Express are full-featured and have been good to work with. They may not have recurring payments, but if not, that's pretty straightforward to implement yourself.
I am in Australia and have a software application that takes subscription payments.
I used NAB as the bank for the merchant account, their fees were the lowest when I checked (and for my predicted transaction volume).
I use Chargify for the subscription functionality, they recently added a very good GST module which makes them the best choice in Australia in my opinion.
I then use payment express for the payment gateway, as they are compatible with both NAB and Chargify.
Other than the delays waiting for the various approvals (particularly bank and payment gateway), it was fairly straight forward to set up, and the only coding required was to integrate with the Chargify API.