What can you do if the Public Certificate you are using on your Edge server(s) is not trusted by Office Communicator 2007 Phone edition? The public certificate is not trusted because its corresponding Root CA certificate is not installed on the device per default. In this post I describe how to make Root CA certificates available on the device.
You can use the certutil mechanism to install the Public Root CA certificate. First you download the certificate from the CA's web site. Then you use the certutil command to publish the certificate to your Active Directory. It will be added as an object under CN=Certification Authorities, CN=Public Key Services, CN=Services, CN=Configuration, DC=<domain>, DC=<tld>. You can add multiple Root CA certificates using this method. The device will download all the certificates found.
After the public Root CA certificate is published you will have to connect the device once to the internal network to get the certificate downloaded. Before you do that you need to reset the device to clear the certificate store, since you need the device to ask for certificates (if you didn't do this the device would use the currently installed certificate when challenged by your internal OCS servers and not search for them in Active Directory). You reset the device by inserting a paper clip in the small hole on the back between the USB and headset connectors. Afterwards you can connect the device to the Internet and it will connect to the Edge server.
PS: The above only works if the device is able to get to your Active Directory domain controller and the way it finds that is through DNS or NetBios. Please make sure this works by following the steps in this document. If you are using UPN style username and the certificate download fails try to use <domain>\<username> style login.