This usually happens if the internet connection you're using is with a different service-provider to the owner of the SMTP host you configured in Outlook Express.
So, for example, if you're on an Eircom hotspot but you're configured to use UTV Internet's SMTP relay for outgoing mail.
If you are on Eircom, then use mail1.eircom.net for outgoing mail, even if your incoming mail is coming from a different server.
Happens a lot when abroad and using hotspots.
One other possibility is that your ISP's SMTP server has been black-listed by the recipient's server because someone else used it for Spamming.