A few years ago departing from Australia without a passport was not illegal.
I checked with Immigration at Brisbane airport when I was asked to board an Australian citizen to POM on a scheduled service without a passport. I was told that it was OK... but not OK to travel TO Australia without a passport.
I cannot comment on other aircraft/AQIS documentation.