This sounds like a relaying issue to me but Vodafone have offered zero assistance. My father uses Spark for his mobile carrier (work phone) and operates a clear.net.nz personal email address. He is able to receive email from pop3.clear.net.nz while on the Spark network. He is intermittently able to send email via smtp.clear.net.nz but for the most part he can't.
Can anybody offer any advice to make this work? Webmail is not a viable solution.
Something I haven't tried is to use Sparks email server but I'm not sure they'd permit a ReplyTo address of clear.net.nz?