Mark,
Yes, this is complicated and hopefully this will help you. The cheapest way is to install your own Enterprise CA and issue your own certs. Send instructions to your users on how to install your CA root certificate in their trusted root store. All domain joined clients will trust your CA automatically so only remote clients will have the problem. Be sure when you generate the request file that you inlcude any possible name that a client will use to access your server and be sure to include the autodiscover address as well. Take your time, follow the steps above and you should be good. If you still need help use the support forums or open a case with MS Support.