Air New Zealand, while not OW, has a great intra-NZ network and a little thing called an Explore NZ AirPass that lets you fly around the country inexpensively. Basic price is NZ$515 (US$225) for three segments and NZ$171 (US$75) for additional segments (max 8). No OW miles but very reasonable fares for what you get. Note that you must book and ticket this from outside NZ and (this could be a killer) it may require you fly to NZ on NZ or a *A partner.