As an ex major bank employee, I can tell you it is definitely illegal. I'm a little too busy right now to find the legislation, but basically a merchant is allowed to pass on the "cost", per se, of accepting the card. So in airlines' case, they can justify some level of administration in addition to the AMEX/MC/Visa fees. However, charging nothing (or say 1/2%) on MC/Visa, but then 10% on AMEX, is absolutely illegal - there is no way they could justify such an inordinate excess charge.
However, the ACCC is of course known as "the toothless tiger"... the best protest is to tell them they've just permanently lost a client over a few dollars.