Can I suggest trying Windows Live mail to see if it does send the emails correctly?
Also, another thing that you can try is to create a new identity and setup the email account again and see if it does it with a new identity.
However, the very first step still is to make sure the anti virus is up to date, and run a full scan