muppet: I can't understand why you're not able to use the Vodafone SMTP server.
Surely it shouldn't care what the "from" address is, as long as you're coming from a mobile IP address you should be free to send mail from and to whom you please.
Or have Vodafone setup their SMTP servers strangely?
Many systems calculate a value for how likely an email is to be spam, they use a barrage of tests that include: HELO/EHLO checking, PTR/Reverse DNS recording, SPF and domain keys... some of those are going to fail when you sending from firstname.lastname@example.org via smtp.yourrandomisp.co.nz which will add to the "spam value" calculated for your message.
Sending from email@example.com via smtp.vodafone.co.nz is a great way to find your email in your intended recipients junk folder or filtered out completely by many anti spam systems