Nagios email stopped working after changing the relay mailserver

My colleague mentioned the other day that our Nagios monitoring was very quiet for the last couple of days. I checked the maillog on the Nagios server, to see that all the mails were in status ‘Sent’. A closer look at one of the records showed that Sendmail was still using the old MX record for the target domain. This record had been changed about a week ago and a
[root@Nagios ~]# dig MX company.domain.com
came up with the new SMTP server. I thought that a restart of Sendmail would fix the problem, but it did not. Bummer!!
The only way to force Sendmail to use the new MX server was to add the following line into the /etc/mail/mailertable:
company.domain.com esmtp:[IP]
Where IP stands for the IP address of the mailserver in the MX record.