Is your Exchange 2013 (Windows Server 2012) putting messages in the DRAFTS folder?
-hard code the IP ADDRESS in the c:\windows\system32\drivers\etc\hosts file as both FQDN and Friendly name.
It will look like this:
192.168.1.2 server.domain.tld
192.168.1.2 server
Restart the MAIL TRANSPORT service and everything should be right as rain.
This happens because the server is trying to use IPv6 and for some unknown-reason-to-me, the IPv6 wasn't working as it should. Hard coding the ip address in the HOSTS file forces the server to use IPv4.
Another 6 hours down the drain due to lack of logs in Microsoft Windows. This is exactly why I stopped using Microsoft software more than 10 years ago. At least with Red Hat (RHEL, Centos, Linux) you have something to go on. If you are business, I recomment getting a support contract so that you can call when you need to.