We had the same problem. I just asked the Certificate Authority to add a “Subject Alternative Name” that matches the internal name to a single certificate. This is through verisign. not sure if other CA will do the same.
email.company.net – Subject Name
another.company.net – Subject Alternative Name
Take a look at my blog entry about certificates and Exchange. This will help you understand why this is happening. The clients need to have a path to or trust the root certificate authority.