I think you need to keep escalating to a manager until you get through to one in NZ. POP, IMAP etc is part of the service, so unless they can prove that the issue isn't at their end, they can't then tell you to go to a third party. Doesn't sound like there is much option to move provider if they can't support their services for you.