Welcome to PressF1 Chris.
You need to check the SMTP server - that's the outgoing mail server.
In Outlook 2003, you need to go to Tools and Account Settings, and select View or Change Existing Accounts.
Double slick on the account (or accounts) and look at the outgoing mail server area.
It should be smtp.xtra.co.nz with no SSL or authentication. Click on the more settings button to check those last two settings.
On the Outgoing Server tab, nothing should be ticked. Make sure "My Outgoing Server (SMTP) requires authentication is not ticked.
Go the the advanced tab, and look at the outgoing server area. It should be port 25, no encryption.
Try again, post with the results.