Hi Glencottage,
The reason you would not have seen these stamps (
CALs) "in the nineties" is that they didn't exist until 2004.
Since NZ first had its own postal service it was restricted to the official carrier, and sometime this was slightly relaxed to permit others to carry customer's parcels & goods weighing more than the letter rate - hense the growth of "couriers".
When New Zealand deregulated their postal system - I think it was May 1998 - anyone who registered with the Ministry of Economic Development & paid a fee (then $95) could operate a mail system delivering
letters (mail), but were required to register what they termed a "postal identifyer" (like a logo or name, mark or design). Each letter (or parcel if that was being sent) would be cancelled with that "identifyer".
The words "NEW ZEALAND" were reserved only to be used by NZ Post, and the new alternate post operators were specifically forbiden under their licence from using those words,
These new operators were at liberty to produce their own "stamps" to indicate pre-payment of postage, however they were not "required" to produce them, and might choose to just have an inked rubber stamp to achieve the purpose.
New licenced operators such as DX Mail, Fastways Post, Posties Choice, Black Sheep, NZM, National Mail, Today's Post, Card Call produced a variety of stamps with prices usually undercutting the "official carrier" (NZ Post). Many wern't destined to last long as they wern't really geared up to adequate cover the areas they promised, or were simply inefficient. As some folded, or were bought out by rivals, the better firms prospered & were joined by a few new businesses who were successful in associated areas -
such as Croxley Mail who were huge manufacturers of envelopes.
All this was observed by NZ Post.
A number of "players" signed contracts with NZ Post for delivery of their letters and so merely became "middle men". For providing a specified quantity of letters to NZ Post they received a "kick-back" payment. I've misplaced the figures, but this was like "for 6 million letters a year they received 5c each for their services".
One of the shortcommings of deregulation was that a proliferation of mail boxes sprang up at shopping centres, etc.

For a short time there might be a dozen different post boxes in a row - you had to use the correct one of face serious delays whilst the letter was returned to "your chosen" company for reposting through their mail system. Having become a sub-contractor for NZ Post reduced (or eliminated) that problem.
These alternate mail companies were also making money by approaching businesses to advertise utilising the "stamps" being printed on behalf of these mail companies.
So there appeared "ads" for New Zealand household companies -
Dickies towels, Stationary Warehouse, Sealy bedding, Whittakers chocolates, Society of Prevention of Cruelty to Animals, Resine paints, The Shoe clinic, Night'n Day foodstores,Wellington stampshow, etc, etc.
NZ Post observed all this successful advertising & moneymaking and I guess there was some type of "thinktank" where they came up with the idea of competing in this field, themselves.
In late 2003 or very early 2004 their first candidate signed up.
The New Zealand Festival in Wellington wanted to advertise their 2004 festival & a new 40¢ CAL (Customised Advertising Label) was printed for the organisers to use on their mail-out. Very little is know about this and there was no word circulated by NZ Post to promote this new venture.
In March an increase in the postal rate was approved to 45¢.
A supply of 5¢ stamps was required to make-up from the stock of 40¢ stamps in circulation & held by the public. Marketing this requirement to the ANZ Bank & later to BMW sales, NZ Post suddenly was "in the bigtime" as word reached the stampworld.
Kiwipex & National Stampshow ordered supplies of 45¢
CALs.
Other advertisers became aware of this facility & placed orders.
And so the proceedure has become available to anyone who submits a design to the Wanganui Business Centre of NZ Post.
If your design is approved you specify how many stamps you require (min. of 1,000) and whether they are to be in sheetlet or peel-and-stick form. Pay you fee (the unit cost is cheaper if you order a larger number) & you will receive the entire order. NZ Post does not supply your designed stamp through post offices, but they issue an "annual pack" of all issues the following year via their philatelic bureau. Because the first five
CALs were of the "experimental" type & subject to a different signed contract, they have never been available through the philatelic bureau.