richms: If you use 2degrees smtp server than expect most of what you send to end up in the spam folders, since many spam filters will look at the dns records even in the absence of a properly formed spf record (which telstraclear appear to lack) as an indication that an email is being spoofed.
If telstraclear wont provide you with a working non port 25 TLS/SSL mail server, then I think that it is clear that it is time to move on from them as they are not serious about providing email.
IMO it is irresponsible for an ISP to accept SMTP auth over cleartext from outside their network.
+1
This is where I normally recommend they take the short term pain of registering theirr own .co.nz domain name and setting up Google Apps Free or Outlook.com (Windows Live Mail for custom domains) as the email host for the long term gain.