After speaking with Kayako support it was determined that the problem lay with our Exchange 2010 server.
On checking the error logs on Exchange I found an Application Error event 12014, under Task Category TransportService;
Microsoft Exchange could not find a certificate that contains the domain name name.domain.local in the personal store on the local computer. Therefore, it is unable to support the STARTTLS SMTP verb for the connector CONNECTOR-NAME with a FQDN parameter of name.domain.local. If the connector's FQDN is not specified, the computer's FQDN is used. Verify the connector configuration and the installed certificates to make sure that there is a certificate with a domain name for that FQDN. If this certificate exists, run Enable-ExchangeCertificate -Services SMTP to make sure that the Microsoft Exchange Transport service has access to the certificate key.
As we recently had to change our email SSL certificate, I checked the Receive Connectors named in the errors and found that the FQDN provided in response to EHLO or HELO did not match the name on the new SSL certificate.
After updating this connector, email began to flow in and out of our helpdesk again.