D'oh, I had no idea, and here I am already having spent months talking to NAB in order to charge USD and support AMEX. Stripe seems a lot cheaper too in terms of fees.
Stripe AU supports AMEX (as well as Visa and MasterCard!), but is currently only for AUD charges. We are actively working on adding USD support, and hope to roll it out soon. Email me @ thairu@stripe.com if you would like a beta invite.
Braintree does Visa, MC and AMEX - both in AUD and USD. Braintree in Australia uses a NAB account up back to allow multi-currency deposits, which is nice.
Stripe in Australia makes me very happy though, and I may have gone down that route for the brand alone if I hadn't already integrated Braintree into my app (with a nice library, to boot).