Does this problem happen with any and all attachments? In other words, do small attachments, such as a single Word file, also cause this behavior?
You say "After restarting the e-mail is shown as sent". Do the messages always, in fact, get sent? Have you verified this with the recipient?