There is only 2 reasons why this happening,
1. The A Party is being incorrectly presented to the service, (Bad... very Bad)
2. The Number range has been marked as a Auckland number local range buy the provider of the 0800 Geographical service. (Most likely)
Marking your call as restricted has no effect btw, the CLI is still available in the messaging it is only hidden to the B Party, networks still see the A Party details.
Take it up with 2talk it's absolutely their issue to chase on your behalf