After a few frustrating days of seraching forums and trying various combinations and permutations I have a combination that works on my phone. Usual disclaimer applies (if it causes the phone to explode, nuclear war etc at your own risk.) I have an HTC Desire running Android 2.2. I have tested pxt and mobile broadband which works. Settings as follows:

Name:
Vodafone NZ
APN
live.vodafone.com
Proxy
172.030.038.003
Port
8080
Username
(blank)
Password
(blank)
Server
172.030.038.003
MMSC
http://pxt.vodafone.net.nz/pxtsend
MMS Proxy
172.030.038.003
MMS Port
8080
MMS Protocol
Wap 2.0
MCC
530 (default value)
MNC
01 (default value)
Authentication type
PAP
APN type
(blank)
 

Hope that helps someone,
Paul