*** Improved by Wrobinson on 09/08/08 ***
Since you are receiving and sending messages in Outlook Express, the root cause appears local to the specific computer and/or copy of Outlook. If Oultook Express is installed on the same computer, then that all but eliminates the computer. I would confirm all of the profile settings in Outlook, particularly the SMTP incoming and outgoing server settings. Make sure that the correct user name and password is entered.
Something that may help troubleshoot this issue is more information, such as how the Outlook client is configured — MAPI, IMAP or POP.
If you are using a MAPI profile, create a new MAPI profile for testing purposes and see if the issue occurs with the new profile.
*** End Update ***
It does sound like something is wrong with your send settings in Outlook. Check the configuration there and also if there might be a firewall along the path blocking outbound SMTP traffic.