I have seen a lot of speculation with getting Nokia Mail for Exchange working with Exchange Server 2007 on the internet & face countless problems with the same myself.

Initially, I thought it "Just didn't Work", I had deployed Exchange 2007 at 2-3 of my clients & each time I tried to connect a M4E mobile device to Exchange it kept failing. Upon examining the logs on the mobile device I found an error something like the following:

"A field in the handshake was out of range or inconsistent with other fields"

Now the thing that REALLY got to me was that for one of the Deployments I did, it Actually worked, the only difference being that I had used ISA 2006 to publish the CAS server for this particular project which the others had not been.

So I thought I had found the answer, but in truth, the next time I tried to do this again it failed, with the same errors.

This time, I knew it actually did work & so I began troubleshooting the problem. A process that ended up taking 2 full days of my time, but rewarding none the less.

* I should point out that at this point I was using an Internal Microsoft Certificate Authority to issue certificates to my servers & installed the Root CA on the Nokia Mobile prior to enable M4E.

In MOST cases I had enabled my internal CA to issue Multiple SAN Certificates & generated CSR's which included the names for my organization using the New-ExchangeCertificate cmd-let as is generally accepted out there, but this always resulted in the issue above.

The time it worked, I had generated the CSR from ISA 2006 IIS with a single Subject Name & then MANUALLY ADDED the SANs at my CertSrv when I generated the certificate.

To do this, in the Attributes field when you request a new certificate type the following (without any Spaces):
SAN: DNS=mail.domain.com&DNS=autodiscover.domain.com&DNS=server.domain.local

Now when you compare the certificates generated in these two different ways, they both appear pretty similar, except for 1 thing - If you look at the Details Tab of the Certificate one of them will have a Yellow Warning Triangle on the Subject Alternative Name attribute & one will have the Good Green Circle on the same attribute...

Now the trick here - When you generate the CSR using New-ExchangeCertificate Cmd-Let it appears that although it generates the CSR & the certificate is issued without any complaints it would appear that the CA somehow understands, but doesn't like, the way the SANs have been added & gives you a certificate which works, but has some warning attached.
 
(I haven't been able to figure out what or why yet so if anyone knows please feel free to enlighten me)

Now Mail for Exchange does NOT like this anomaly in the certificate & as such WILL NOT connect to the exchange server & download the mail.

However, if you have a nice Green Circle in the SAN Attribute (Added SANs Manually when you request the Cert) then all seems to work perfectly well provided you have put the Root Certificate on the phone too.

The Good News, however, is that this ONLY applies to Internal Certificates - It appears that once you upload your New-ExchangeCertificate CSR to a Public Trusted CA they "Normalize" the certificate before issuing it to you & your M4E will work after the Public CA Certificate is deployed on your Exchange / ISA Servers.

It should also be noted that you need to make sure your Mobile is running a revision of Symbian OS newer than 1.5 (I think it is) to be able to handle Multiple Subject Name Certificates.