Not sure if this is relevant since your messages get sent eventually, however - The stored credentials sometimes seem to get corrupted.
Control Panel\All Control Panel Items\Credential Manager
Windows credentials
delete all MS Office credentials
You will need to log on to accounts again.
Above was for a Domain environment - not sure how it applies to your situation.
I was 1st line support and had no idea what was really going on.