I'm having a similar problem. The attachments I send are around 50KB Word documents using Entourage, Mail (both use DotEasy's SMTP service on port 587), or the Web mail from my Web site (DotEasy). I've also used my ISP's Web mail with the same result. Occasionally an attachment arrives safely in the recipient's inbox, but usually I have to upload it somewhere and send a link for the recipient to download it. Very occasionally, messages without attachments haven't been going through. No error messages, either. If it didn't work all the time, it would be easier to figure out, but sometimes it does work. Really frustrating.
What I do step by step: Wake up MacBook. Click Entourage icon in dock (Entourage is open already), receive messages and send replies. Open Word and open an existing document, or open and save new Word attachment (from an e-mail message) and then edit it with Track Changes. Save and close Word document. Click Entourage icon in dock. Select message to reply to. Click Reply. Compose message. Click Finder in dock. Drag Word file to message to attach it. Click Send. Check e-mail later and receive message asking whether I've sent the file.
I wonder whether it would help to
1) quit and re-open Entourage daily
2) click Attach while composing a message rather than dragging a file onto the message
I've forwarded or CC'd messages to myself when I send them, and it looks like the ones that don't make it to my inbox are the ones that aren't making it to anyone else's inbox, so at least I can tell whether something's gone missing. (Darn it--I was wrong. Some of the forwards arrive safely, while the originals, sent to another addy I have, are going missing.)