Nada más deberías renovar el certificado en Exchange, pq lo que tienen tus clientes es el certificado de la CA y si el mismo todavía no expira no necesitas renovar el mismo.
Para renovar el certificado de OWA de Exchange 2003 es muy similar a cuando lo hiciste por primera vez, con la diferencia que si no recuerdo mal hay una opción para renovar:
http://www.msexchange.org/tutorials/SSL_Enabling_OWA_2003.html
Debajo del título "Creating the Certificate Request"
Saludos,
Dario Woitasen | MCITP: Enterprise Messaging Administrator 2007/2010 | MCITP: Lync Server Administrator 2010