I had the same problem with Belgium. Safari always looks in Google France.
To solve my problem, I had to modify Safari binary (/Applications/Safari.app/Contents/MacOS/Safari) with an hexadecimal editor.
I only replace
http://%@.google.com/%@?q=%@&ie=UTF-8&oe=UTF-8 by
http://%@.google.be/%@?q=%@&ie=UTF-8&oe=UTF-8
As I've a byte missing '.com' --> '.be', i put a blank before the http, so the size stay the same.
Now, when I do a search, it search using Belgium Google.
The only backdraw of this, is the fact that I must do the hack, everytime Safari changes.
I hope, this can help.
Cheers
Edit:
Oops, it may not help, because in your case, you have two letters more '.com' --> '.co.nz' and not less.
What you can do, is do the same, and remove unecessary parameters such as 'ie=UTF-8' or 'oe=UTF-8', so you gain place
and put as many blanks as necessary before http.