Outlook/Exchange certificate errors after setting clientaccessserver, etc... properties

After updating exchange 2010 using the commands for Set-ActiveSyncVirtualDirectory, Set-ClientAccessServer, Set-ECPVirtualDirectory, Set-OABVirtualDirectory, Set-OWAVirtualDirectory, & Set-WebservicesVirtualDirectory to point to the same address as our external address with appropriate DNS entries to forward this address to our mail server, all new Outlook accounts that are setup function perfectly however old accounts are still throwing up certificate errors about 20-25 seconds after Outlook starts. I’m guessing that the existing accounts are using some cached data to connect that the new accounts are not.

Does this guess make sense?

What can I do to force these clients to update their cached data?

If not, is there a way to recreate these accounts while preserving the user address books, etc… (preferably in a scripted fashion)?

Background:

We have users on domain-connected PC on our internal network and external users accessing the exchange server through OWA on non-domain connected computers. For our internal users, everything was good (except for the fact we were using outdated security) but for external users they were constantly getting errors regarding our SSL certificate. So, we acquired a certificate from a trusted CA and we installed it on the IIS Server. As expected, all of the errors disappeared from our external users, but we ended up having errors for people accessing the exchange server on the domain PCs through outlook. The errors made perfect sense, the IIS server was presenting a certificate for a different domain than those computers were connecting to. A little searching around found this question on server fault, which got me to the point where new outlook accounts are setup fine, but old outlook clients are still throwing up errors.