When have this issue in Exchange 2013, you can try to perform below :
1) Open Exchange Management Shell in malbox server
2) issue below command
o Restart-Service msexchangesubmission
o Restart-Service msexchangedelivery
o Restart-Service msexchangetransport
So far no impact to database, we only restart the transport services in mailbox server. Then try again to see either it’s working now.