Some years ago Australia Post did an article on RASS/Australia Post mail services.
I seem to recall the Port Augusta Airways service to Birdsville (and Mt Isa??) was the longest, however one of the Cape York Air services was the longest one day air mail service.