In reply to John2: Three are correct in that to send email - regardless of what address you are using you will need to use their SMTP server - that's normal practice.
However, even if you're not using a Three email account you may need to use a Three username and password to access their server. That is the set-up I have with outgoing mail on my mobile phone - I can set my email address to any account but I still have to use my Orange username and password.
However, if the server can't be found it's either going to be a slightly incorrect address or something less easy to reslove.