The hack emerged after the teen sent the mailbox details to New Zealand IT site Computerworld.
The victims included senior communications managers for the Army, the Air Force, the Department of Internal Affairs, the Police, and Mayor Dick Hubbard of Auckland.
According to reports Telecom, which runs the service, will be contacting nearly three million of its customers to find out whether the optional Pin service, the source of the data compromise, should be kept.
"Telecom takes the security of its customers' voicemail seriously," said John Goulter, public affairs manager at Telecom. "We're putting every effort into making sure they are as safe as possible."
In other Southern hemisphere computer security news Australia's Victorian Ombudsman has called for a police database system to be withdrawn after repeated allegations concerning its misuse.
Correct usage of the Law Enforcement Assistance Program (LEAP) was apparently misunderstood by Victoria Police.
"It is clear that without the immediate replacement of LEAP as the force-wide computer based information system there is serious risk of the system's continuing vulnerability to improper accessing and release of data," said George Brouwer director of Police integrity in Victoria, in a statement.