After checking the event logs on the affected RDS Server, there were event 25 'Network problems are preventing connection to Microsoft Exchange' and 26 'Connection to Microsoft Exchange has been lost. Outlook will restore the connection when possible'.
I logged a call with Microsoft. The first thing they said was to upgrade to Exchange 2010 SP3 with the latest rollup (rollup 5 at time of writing).
Microsoft then said the issue with error 25 and 26 is often due to a time limit between Outlook and Exchange. This default 'keep-alive' (or time out value as it is also known as) is 120 mins.
If the RDS Servers, or any proxy, switches or firewalls between it and the Exchange Server have their own 'keep-alive' timeout values set to less then the default 120 mins, this can cause the error as connections are broken and re-established. More information can be found in the following link http://support.microsoft.com/kb/2535656
Although Microsoft insist this is usually the issue, I wasn't convinced this was the cause of our problems as we had been running the same RDS Servers, Exchange Servers and switches for a couple of years. We put in a new proxy and firewall a couple of months back but had seen no issues until very recently.
So, what else had changed?...
We recently carried out a full review of our AV, updating the software and policies. I checked the McAfee logs and altough there was nothing really standing out as the definitive cause of the problem, I did notice that at the times of errors 25 and 26 there was a lot of scanning taking place from the On-Delivery Email Scanner.
The On-Delivery Email Scanner scans all emails as it is delivered to the email client (Outlook). Not ideal on RDS Servers that have many users on there as would cause a lot of activity.
McAfee say "You can choose not to use the client side scanning because protection is already provided on multiple layers, such as on the Server side and Perimeter, or if the email is received via an unsupported protocol"
As it says, if you perform email scanning at differnet layers, for example, on-access scanning on clients (McAfee VirusScan Enterprise), Exchange-aware AV on the Exchange server (McAfee Security for Exchange/Groupshield), or scanning on the perimeter (such as Websense, Message Labs or Mimecast) then it is safe to disable the On-Delivery Email Scanner.
Since disabling this via McAfee ePolicy Orchestrator we have had no reoccurances of the issue.