In case anyone else is in the same boat as me:
My ISP is TelstraClear, I have an Xtra email address, and I use the beta of Windows Live Mail in Windows Vista to access my Xtra email via Xtra's 'Remote Mail' service which allows you to download your Xtra email through another ISP. This requires different server settings in your email program than if Xtra is your ISP.
Since my email stopped working on Saturday and I wasn't able to send/receive emails anymore I have been trying in vain to get it working again trying various settings, the settings that Xtra said it should be, and suggestions from other web sites but nothing worked until now. If you use Xtra's Remote Mail service and you can't access your email then try these settings, which now work for me:
pop3.xtra.co.nz and send.xtra.co.nz
'email@example.com under the 'Incoming Mail Server'
Tick the box for 'My server requires authentication'
SMTP port 25 (SSL not selected)
POP3 port 110 (SSL not selected)
As far as I'm aware these settings haven't been posted anywhere else and I got them just from playing around with them. Why they even work I don't know, especially as they aren't even the settings that Xtra say they should be. I can only assume they will work in Outlook, Outlook Express and Windows Mail as well.
So if this only helps one person then I'll be happy as I've been VERY frustrated the last few days trying to get my email working again!