Is your active directory domain setup as domain.com?
Getting A UCC certificate _is_ going to be the easiest way to fix (I know you dont want to, just putting it out there, it is the CORRECT way to do it)
This deals with a lot of the concepts that you are trying to work with (it is for 2007 but it is the same in 2010)
http://technet.microsoft.com/en-us/library/bb332063(EXCHG.80).aspx#OutlookAndADYou can look at setting up certificate services on your domain and creating a CSR from exchange and issuing it from your own CA.