I'm having exactly the same problem.
I'm running a 7.2 server on a network and some of the users are on outlook express and some are on outlook 2003
The outlook express is working fine. Outlook is not
Another problem with the mail is when MYOB ( accounting package ) tries to email an invoice. It creates the PDF invoice and attaches to an outlook express email and tries to send. It brings up a message "emails without a date header are not accepted here".
You click on the out box and click on the message and click on send and it will go without a problem.
I think I might have the same problem with both MYOB and Outlook. The mail server is being too picky about what it will and won't send to the point that M$ mail products are not compatible with it.
I think if Outlook gave a real reason for failing instead of dribble it might say the same as MYOB
Thanks
Bruce