I am in Auckland and I use a service provided by an outfit called 'more than print' on Khyber Pass Rd.
Sad to have to say this but I have to withdraw that suggestion.
I went to pick up my post today and, along with a couple of letters was a notice telling me that the service will be shutting permanently in a few weeks time.
So now, I have to find an alternative.
Best I have come up with so far is an outfit right in the CBD that markets a mail service to backpackers.