Playing around with Flight aware tonight and discovered Awesome Aviation (B1900 lease company based in Perth) Beech 1900C VH-EMK flew from Perth to Cairns (including a night stop in Townsville) mid last week. The aircraft is still in Cairns according to Flight Aware.
Very good chance this is the extra 19 seat aircraft mentioned in the press release.