First of all, try to restart the Windows service “Simple Mail Transfer Protocol (SMTP)”

If that does not clear the queue, there might be a DNS lookup problem on your server. If the server is unable to resolve the mail exchanger (MX) record IP address for the mail server it is trying to deliver to, messages will not be delivered.

Check the Event Logs for entries similar to the following:

Event ID: 4000 Source: SMTPSVC
Event Type: Warning
Description: Message delivery to the remote domain “contoso.com” failed. An internal DNS error caused a failure to find the remote server. 0000: c00402e7

Check the settings for your network interfaces to make sure the DNS servers listed are accurate.