The MapPoint Web Service now includes data for New Zealand. Here's an article describing the changes in the release that has just occurred.
See also the MapPoint Developer Centre and you can get a 12 month free subscription as an MSDN Subscriber. Go to the MSDN Subscriber web site, log in and look under the "Cool Offers" section. If you aren't an MSDN Subscriber you can still get a 45 day trial of the MapPoint Web Service.
Go on, try it out..