I've had exactly the same problem, just recently. Using OS X 10.3.9, with Entourage X, I have just recently encountered problems sending emails. Never had this problem before. But it doesn't have to do with sending HTML format. I can send a simple email with HTML, no problem. The problem occurs when I try to add an attachment, or have multiple email address in the CC: or BCC: address field. Very annoying!
I'm quite sure it does not have to do with the STMP protocol on the email server, since I was able to send an email with attachment via WebMail on the same server.
My suspicions are that it may have to do with the recent OS X update, but that's only a guess.
If anyone else is having this same problem with Entourage (in Office X), I'd like to hear from you. I'm wondering if upgrading to Office 2004 would solve the problem.
I did a disk verification (using the Disk Utilities) and I did discover that the Permissions in the Entourage database had errors. Perhaps this is the problem? I've not been able to repair the Permissions -- Disk Utilities returned the notice that repair of the Permission was unsuccessful.