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.