I am currently looking for a decent Pocket PC map solution for New Zealand, and although the Microsoft MapPoint Service offers adress level (not routing) New Zealand data, there is no Pocket Streets maps for this country yet.
Actually, until a few months ago the Pocket Streets 2005 Downloadable Maps page had links to Pocekt Strets maps of Australia and Brazil, now all removed. I don't know why, and lucky I have downloaded these maps while they were available.
A local alternative is the Navman NavST software, but the software doesn't seem to be available in retail stores around here anymore. By the way, most people don't know that Navman is actually a New Zealand-based company.
Back to the topic of this post... While looking for GPS software I came across an interesting article on how Navteq loads the data into their mapping solutions. It involves a GPS-enabled car, a pilot, a co-pilot, hours of driving and voice recordings with POI (points-of-interest). Interesting read if you want to find out more about this technology.