Office Communicator and cannot sync Address book error

Apparently I didn't read your second edit the other day. So if the CRL is the issue, there's a couple of options you have - the best option is to have said admin staff do the right thing with the CRL, which is to publish it to Active Directory. That's a simple matter of using certutil -dspublish. You also have other options, however. Some CAs (root CAs in particular) have a best practice where you don't even publish a location for a CRL. A CRL only needs to be located if the CA says that you should be able to locate it, primarily through the AIA or CDP. I'm guessing based on your description that the CDP has an HTTP url for the CRL (okay, the acronyms are ridiculous, sorry) and that either the CRL wasn't actually put in that location, which has to happen manually, or that location isn't available since as you've pointed out, it doesn't have an HTTP server on it. You can work through this issue; however, I think you'll be better off if you just publish the cert to AD and call it good enough. Note: if the CDP doesn't specify an LDAP location for the CRL, you may be SOL - they may have to redo a lot with the PKI in order to get that set up correctly. However, I've made the same mistakes myself in the past and it's worth fixing.

So, hey, Server Fault! Do you have any badges for >20 acronyms in a single paragraph?

There's no reason why your users should not be able to log in using their e-mail account identity provided OCS has been configured correctly to use the user@company.com SIP URI's and DNS is set up properly. There are number of configuration areas where you will need to check that but pay particular attention to the certificate configuration. I've seen this sort of failure when not all of the SAN's were correctly set up on the certs and when the various DNS SRV records were incorrect. You can find a brief outline of the steps you need to follow to get it all working here and there's some pretty OK simplified installation documentation at OCSPedia.

As it stands it's also possible that your end users just need to apply the Communicator Roll-up Hotfix from KB969694. Presence failures related to Outlook Integration can be resolved by this if the issues are simply a client side problem.

I'd still recommend you take a good look at the Cert\DNS configuration in your environment as you really should be able to get users to simply install Communicator and have it "just work".

The changes you need to make are:
Your internal (and external if you want external access) DNS settings must have A records for all of the OCS services (SIP, web-conferencing, AV etc). If Communicator is working at all then these are probably OK but worth checking. Ideally you should also have DNS SRV records for the autodiscovery names ( these are _sipinternaltls._tcp.company, _sipinternal._tcp.company.com, _sip._tls.company.com and _sip._tcp.company.com ) that point to the Front End server so that the auto-discovery process will work properly. The specifics are summarised here. Autodiscovery will still work even without SRV records provided you have the relevant aliases (_sipinternal.company.com etc) setup as A records in DNS. Communicator tries a number of alternatives before failing which is why you can get away without SRV records but it is best to create them if you can.

The DNS changes are reasonably straightforward if you are not using Certs but if you are using Certs (which you will have to for external access) then you will need to take care to configure the certs appropriately too - again the steps you need to follow for creating Certificate requests, installing and configuring the services to use them are available in this OCSpedia page. The definitive documentation for all of this from Microsoft can be downloaded from here and I'd recommend that you take time to work through it if you can, the OCSpedia and blog links should suffice but they are a simplified set of steps.

To change the name users log into communicator with from username@company.local you have to add company.com as a SIP domain in the Front End Server Pool. If you right click the Pool in the OCS Manager then you should be able to get into the Configure Pool/Server Wizard to do that.