I had the same problem using Outlook 2003. After I changed the following setting, email delivery worked without problems:

Settings → Active Protection → Mail Shield → disable “Scan outbound email”

Warning: The last porgram update overrode the setting and the problem was back.