I am asked about OCS/UM certificates quite a bit lately and I am always forgetting off the top of my head who is providing the certificates. Choosing a provider is key for PIC (interaction with public IM networks) and ease of federation with other companies. One pain point you can avoid by going with a "big name" is that they are most likely already a trusted authority in your smartphones and computer systems.
If you want a list of providers that have been 'blessed' by Microsoft for UM certificates, read KB article
929395.
Update #1: Tom Pacyk left a great comment about this entry:
"What you don't see though is that there's only ONE of those that shows up by default in XP, Vista, Mobile 5, and Mobile 6 and that's Entrust. We've been recommending them to our clients for certs and it's worked out great.
As far as defaults...
GoDaddy and Comodo aren't in Vista.
Comodo and Digicert aren't in WM5.
Digicert is not in WM6.
Update #2: One of the things I love about this site is that I get almost immediate feedback when something I post is either popular, or incorrect. In this case, Digicert contacted me to let me know that due to an agreement between EnTrust and them, the information about DigiCert in Update #1 is not accurate. I don't want to spread false information out there so that is why Update #2 exists.