"Mail not Sent" and subsequent message

I am regularly getting an email stuck in the outbox. I then get the message - couldn’t send…check your settings etc etc
Everything else works fine, but this is very annonying. I have to open GMail and send it from there. When I do everything is fine so it isn’t my connection (Super fast speed and everything else connected isn’t affected.
This has been going on for ages and I just got an update…no good!! First email failed.
Anyone any suggestions?

As a test, completely disable your anti-virus/firewall application and see if there is any difference.