I guess it depends on what you offer your existing clients now. if they are connecting to mail.client1.com, does it have a correct ssl certificate? If you don't have any existing clients using an ssl connection method then you might get away with the cnames.
I know moving clients to new servers is always a problem unless you are a big company with huge resources, there never seems to be an easy way.
Theres not much I can help you with about moving existing clients to new servers - best bet is to test it with a dummy setup and see what happens yourself, and see what you can do to get around the problems.
I do suggest however, if you are going to have multiple servers to serve your clients you look deeper into having all your servers under the one domain and using a wildcard ssl. if you hunt around you can get a wildcard for a reasonable price - compared to buying individual certs for server1, server2 etc. It's something to look into as it helps with a number of other things not just mail. Maybe check out places like godaddy and search around for coupon codes - you can often end up with a price not that much different to buying a couple of standard certs.