Introduction of a New CAS Server Causes Certificate Prompts

An increasing issue appears to be a certificate prompt being seen by Outlook 2007 and higher clients following the introduction of additional CAS servers, or new multiple role servers holding the CAS role. 

While this has been an issue for some time and well known to those running a multiple server environment, the increasing number of postings on forums about this problem has probably occurred as single Exchange 2007 servers start to get to end of life and people migrate to Exchange 2010. 
The cause of this is usually autodiscover. 

What is Happening
CAS Servers have a value called "AutoDiscoverServiceInternalUri". This is published in to the domain as a Service Connection Point (SCP) and is queried by Outlook 2007 and higher as part of the internal autodiscover process. It tells the client where to connect to for the account information. 
If you have multiple CAS servers then they will all be publishing this information to the domain, in effect overwriting each other. 

This command will show you the name and the value set on all Client Access Servers in the org:

Get-ClientAccessServer |select name,AutoDiscoverServiceInternalUri

The Resolution
There are two resolutions to this issue, depending on your setup, and future plans.  

1. The simple fix is to bring forward the introduction of the trusted SSL certificate and get it installed on to the new server. The value for "AutoDiscoverServiceInternalUri" should match one of the host names on the SSL certificate. Remember that most SSL providers will not allow multiple certificates with the same names on them to be issued, so you may have to get a new certificate issued to cover all servers with the CAS role. 
2. Set the value for AutoDiscoverServiceInternalUri to be the same on all CAS Servers. If this is a specific server name, rather than a generic name, then you will need to change that value on all servers if you remove that server from production. Alternatively you could ensure that autodiscover.example.com resolves internally on your network to the IP address of a CAS server, then set all CAS servers to use that value. Then when the servers are changed, all you need to do is update the DNS. If you have clients on your internal network which are not members of the domain, then you may well have already configured this. 

Multiple AD Sites
If you have your CAS servers in multiple AD sites, then you may well have to consider using site scope to control which server the clients will connect to. There are other things to consider if this is the best thing to do or not and this Technet article explains how to use Site Scope: http://technet.microsoft.com/en-us/library/aa997633(EXCHG.80).aspx

CAS Array
This is not related to the Exchange 2010 CAS Array function, and you shouldn't use the CAS array host name for this. The CAS array doesn't use HTTPS and also shouldn't be resolvable from outside.