Also are you sending mail via the built in windows client (IE outlook, thunderbird) or via direct SMTP?
Any possible changes to the SMTP account you can think of?
I wonder if you change default email apps or go to another machine with a different email app, if it works. I've seen funny things with Outlook someimtes. I agree with Mike, if possible, send directly to the SMTP server and skip the inbetween Email client when possible. Much more efficient. The only reason to use the client is if you want the user to add some text to the email message such as a personalized note.