There were a couple of Herc operators, firstly Transamerican with an L100, who used the callsign "tee-vee ten" (not sure what the rego was) and operated Nadzab-Tari for 2 or 3 months.
In 1982 when the Fly River dried up Cargomasters (an Australian company) operated 2 L100's VH-CYO (which ironically is now operated by Lynden Air Cargo who hold a PNG AOC) and N106AK. These two aircraft operated Madang-Kiunga and also only lasted 2 or 3 months. Cargomasters folded soon after this contract ended.
http://www.adastron.com/lockheed/hercules/h1vhcyo.htm
Southern Air Transport came and went a few times, but did not operate internally in PNG.