I had this for a while, especially when paying for things via Apple Pay online (card worked fine on watch and phone with paywave) - was incredibly frustrating. I can't entirely remember what the eventual fix was - but if memory serves me right it was to do with the suburb field

Once I had Wellington in Suburb and City it seemed to start working perfectly

Does your address show up on other sites where you have to begin typing it, then select the correct one from a pre-populated list - eg. as on this NZ Post site?:

https://www.nzpost.co.nz/tools/address-postcode-finder