They were delivered by the New Zealand frigate Canterbury and special New Zealand envoy John Hayes, a former high commissioner to Papua New Guinea, pledged his country's door would remain open to help achieve peace.
New Prime Minister Bill Skate has created a Bougainville portfolio for the first time and heralded a fresh policy as gestures towards a peaceful solution.
Praising the release of the captives, Skate said: "This is seen as a positive gesture by the New Zealand government which will enhance the existing good relationship between PNG and New Zealand."
New Zealand brokered the first major meeting between Bougainville rebel leaders and the PNG government on board the navy vessel Endeavour in 1992 which became known as the Endeavour Accord.
It also supported the deployment of a regional peacekeeping force with logistics support in 1994, before arranging the recent crucial two-week-long talks between the rebel Bougainville Interim Government (BIG) and the PNG-backed Bougainville Transitional Government (BTG) at Burnham military camp in New Zealand's South Island.
The Burnham Declaration called for a ceasefire, an end to a military blockade of Bougainville, demilitarisation, and installation of a United Nations peacekeeping force. Papua New Guinea was not represented at the talks.
Calling for an end to mistrust and a commitment to peace on both sides, the influential Post-Courier newspaper said: "The gesture by the rebels could only mean one thing - that they want a negotiated peaceful settlement of the conflict."
Founding Prime Minister Sir Michael Somare, who late last year led a delegation of MPs to Bougainville, unsuccessfully trying to negotiate the release of the captives, called on Papua New Guinea to declare 1997 a year of prayer for lasting peace on Bougainville.
The bitter conflict has cost several thousand lives through fighting and lack of medicines and humanitarian aid; led to serious allegations of human rights violations by PNG forces and the rebel BRA; and economically has nearly forced Papua New Guinea to its knees.
Papua New Guinea has also been traumatised during the past five months over a controversial $36 million deal with British-based mercenary company Sandline International to intervene on Bougainville and reopen the giant Panguna copper mine.
The plan was scuttled in March by former military commander Brigadier-General Jerry Singirok who publicly condemned it and ordered elite special forces to arrest about 70 foreign mercenaries and expel them.
Singirok, who has often declared the Bougainville conflict needed solving politically not militarily, was sacked by the government and faced a charge of sedition.
Prime Minister Skate, 43, had barely been in office for a week when soldiers staged a fresh mutiny, seeking a general amnesty for military personnel and non-government organisation activists charged over protests against the Sandline affair.
Skate, a born-again Christian, ordered the police to put on hold all charges against military and NGO activists.
He also appealed for his cabinet to be given a chance to be fully briefed on the Sandline affair and for a revamped inquiry into corruption allegations to be completed.
But already his government is facing credibility problems.
Although Skate came to power on pledges of fighting corruption and never working with the former coalition government of defeated Prime Minister Sir Julius Chan's People's Progress Party and Chris Haiveta-led Pangu Pati, his first moves have caused public unease.
He has included both parties in his coalition government, led by his own People's National Congress, and he has retained Haiveta, who was implicated in the Sandline affair, as Deputy Prime Minister.
Skate, who is the first ethnic Papuan from the country's southern region to be elected Prime Minister since independence in 1975, has gained a formidable reputation for his administration as governor of the National Capital District with a population of about 300,000 people.
However, he faces a difficult balancing act trying to meet pressure by a group of NGO independents in his government for a new Sandline inquiry while placating his former government allies.
But for young Cliffton Kalinau, the captive policeman's son, Skate's government is doing the right things. It helped his father come home safely from Bougainville.
David Robie is a New Zealand journalist and author specialising in Pacific affairs. He is currently lecturer in journalism at the University of Papua New Guinea
