The first step was to reconfigure the Virtual Directories for AutoDiscover and Outlook Anywhere to confirm they were using the mail.domain.com FQDN. The following PowerShell command can be used to set the Internal AutoDiscover URL;
Set-ClientAccessServer -Identity CAS01 –AutoDiscoverServiceInternalUri https://mail.domain.com/Autodiscover/Autodiscover.xml
The Outlook Anywhere directories can be configured using the ECP, click on Servers and then Servers again click the Client Access (CAS) servers and use the Pencil tool to open the configuration window. Click Outlook Anywhere and ensure the directories are set to mail.domain.com.
I then created an SVR DNS Records for AutoDiscover, this is done using DNS Manager. Right click on the Forward Lookup Zone for your domain and select Other Resource Record, scroll down and select Service Location (SRV) and click Create Record...
Fill in the New Resource Record details as shown below.
Expand you domain and then _tcp and you should see an SVR Record for _autodiscover.
Now if you re-launch Outlook there are no certificate errors. Although this worked for me in this instance due to the broad nature of this error this may not off course resolve the issue in your environment.