DHpilot,
As have many of us, and a lot longer than 30 years.
Interestingly, two phone calls have produced two different answers, and neither was clear about a private flight versus RPT.
Despite this all happening several years ago, confusion reigns (or is that rains).
Nobody said there was no paperwork, that would be too easy.
Tootle pip!!

Leadsled, you need to consider the following. That which is emboldened are direct quotes from relevant official information and that which is italicised are my comments/queries:-

The Norfolk Island Customs Ordinance 2016 will apply a modified version of the Customs Act 1901 and associated regulations on Norfolk Island. This means that people and goods arriving in, and leaving from, Norfolk Island will remain international movements for customs purposes. Inbound from anywhere (including Australia) is an International flight as far as Norfolk customs is concerned. You require a Certificate of Clearance from the country of origin (last port) in that case. How do you achieve that from a non-customs (ABF) airport of departure?

All arriving aircraft will be subject to customs clearance formalities, including providing a copy of the last port Certificate of Clearance (or equivalent) to ABF. i.e. you get one of those from the departure aerodrome which is a customs aerodrome - see the previous comment. And, this from the AIP’s “the Certificate of Clearance gives the aircraft permission to depart the airport”. I’m unaware how you get that at a GA or private aerodrome?

The pilot or aircraft operator must obtain a Certificate of Clearance from ABF before the aircraft can depart from Norfolk Island. Try getting back into mainland Australia without heaps of drama if you don’t have one – and where do you present that upon arrival? At a customs (ABF) aerodrome – it is still an international flight for customs purposes despite it coming from Norfolk Island.

Duty-free concessions will continue to apply to passengers arriving in mainland Australia from Norfolk Island. How are these concession provisions assessed if you do not arrive at a customs (ABF) aerodrome when you return to Australia?

“when all the explanatory material refers to airline flights,” - not the case. There is some reference to airline flights operating from International terminals but plenty of occasions where the reference is “This information is for pilots, aircraft operators and freight forwarders for reporting aircraft, air cargo, passengers and crew arriving in Norfolk Island.” That’s not airline specific.

“and neither was clear about a private flight versus RPT.” – I’m assuming the phone calls were to ABF. If they can’t offer a clear distinction there it’s pretty sure there isn’t one.

" I can see no legislative mandate that the aircraft must have departed from another ABF controlled facility" - again, where do you get the Certificate of Clearance if you don't depart from such an aerodrome?