SQL Mail Failing To Send SQL Sever 2016 with the latest updates. Running on WS2012R2. Following error message is received:


  The mail could not be sent to the recipients because of the mail server failure. (Sending Mail using Account 5 (2017-04-14T21:34:10). Exception Message: Cannot send mails to mail server. (The operation has timed out.).  )


I have tried several ways of setting up Database Mail, a mixture of precreated scripts and following the interface in SSMS. 

I have also tried two different mail server credentials (Google and a Web Hosting Company), and both fail with the same error.

The Web Hosting Credentials are used on a PHP Script on another Server which works perfectly fine.

What should I check to get this working?
I was having a different issue about a month ago. I came across this script that should help troubleshooting.

 USE msdb
 GO

-- Check that the service broker is enabled on MSDB. 
-- Is_broker_enabled must be 1 to use database mail.
SELECT is_broker_enabled FROM sys.databases WHERE name = 'msdb';
-- Check that Database mail is turned on. 
-- Run_value must be 1 to use database mail.
-- If you need to change it this option does not require
-- a server restart to take effect.
EXEC sp_configure 'show advanced options', 1;
GO
RECONFIGURE;
GO
EXEC sp_configure 'Database Mail XPs';

-- Check the Mail queues
-- This system stored procedure lists the two Database Mail queues.  
-- The optional @queue_type parameter tells it to only list that queue.
-- The list contains the length of the queue (number of emails waiting),
-- the state of the queue (INACTIVE, NOTIFIED, RECEIVES_OCCURRING, the 
-- last time the queue was empty and the last time the queue was active.
EXEC msdb.dbo.sysmail_help_queue_sp -- @queue_type = 'Mail' ;

-- Check the status (STARTED or STOPPED) of the sysmail database queues
-- EXEC msdb.dbo.sysmail_start_sp -- Start the queue
-- EXEC msdb.dbo.sysmail_stop_sp -- Stop the queue
EXEC msdb.dbo.sysmail_help_status_sp;

-- Check the different database mail settings.  
-- These are system stored procedures that list the general 
-- settings, accounts, profiles, links between the accounts
-- and profiles and the link between database principles and 
-- database mail profiles.
-- These are generally controlled by the database mail wizard.

EXEC msdb.dbo.sysmail_help_configure_sp;
EXEC msdb.dbo.sysmail_help_account_sp;
--  Check that your server name and server type are correct in the
--      account you are using.
--  Check that your email_address is correct in the account you are
--      using.
EXEC msdb.dbo.sysmail_help_profile_sp;
--  Check that you are using a valid profile in your dbmail command.
EXEC msdb.dbo.sysmail_help_profileaccount_sp;
--  Check that your account and profile are joined together
--      correctly in sysmail_help_profileaccount_sp.
EXEC msdb.dbo.sysmail_help_principalprofile_sp;

-- I’m doing a TOP 100 on these next several queries as they tend
-- to contain a great deal of data.  Obviously if you need to get
-- more than 100 rows this can be changed.
-- Check the database mail event log.
-- Particularly for the event_type of "error".  These are where you
-- will find the actual sending error.
SELECT TOP 100 * 
FROM msdb.dbo.sysmail_event_log 
ORDER BY last_mod_date DESC;

-- Check the actual emails queued
-- Look at sent_status to see 'failed' or 'unsent' emails.
SELECT TOP 100 * 
FROM msdb.dbo.sysmail_allitems 
ORDER BY last_mod_date DESC;

-- Check the emails that actually got sent. 
-- This is a view on sysmail_allitems WHERE sent_status = 'sent'
SELECT TOP 100 * 
FROM msdb.dbo.sysmail_sentitems 
ORDER BY last_mod_date DESC;

-- Check the emails that failed to be sent.
-- This is a view on sysmail_allitems WHERE sent_status = 'failed'
SELECT TOP 100 * 
FROM msdb.dbo.sysmail_faileditems 
ORDER BY last_mod_date DESC

-- Clean out unsent emails
-- Usually I do this before releasing the queue again after fixing the 
problem.
-- Assuming of course that I don't want to send out potentially thousands of 
-- emails that are who knows how old.
-- Obviously can be used to clean out emails of any status.
EXEC msdb.dbo.sysmail_delete_mailitems_sp  
  @sent_before =  '2017-03-16',
  @sent_status = 'failed';