RickAvlonitis: Thanks, but at the bottom is a very familiar message:
"Applicants for this position should have NZ residency or a valid NZ work permit."
I found a recruiter willing to work with the fact that I don't have a work visa yet.  It seems that to get a work visa, one needs a job offer too.  I can come on a visitors visa, but I don't want to go down that road yet.

Our company often recruits overseas folk and assists in getting visas etc. In fact we are the 'approved' employer list or something to that affect which speeds up the visa process. We've also had our niche area added to the skills shortage list. So good companies are out there. Many use the visa thing to keep the spam down but most will see past that fact if you have the skills (employment agencies may not do it though so go for company run ads). If I were you I'd send my cv anyway.

BTW we came on a visitors visa but that was pre 2000 and it was almost impossible to get a generic work visa back then.