So you've got a Lync 2013 server with Enterprise voice rocking along like a flipping champ. You've got Exchange 2013 throwin' mail around like it ain't no thang. Shoot yeah, you're a boss. Flipping need some of that delicious auto attendant and some voicemail though amirite? You gotta get UM talking to Lync. The MS documentation for this is a huge wad of mysterious wizardry veiled in vague terminology and poorly-written technet articles, so ignore that flipping junk (I recommend this post for the preliminary UM setup junk. Even though it's for 2010 it works fine - http://blog.schertz.name/2010/11/lync-and-exchange-um-integration/). The one thing that seemingly noone flipping documented anywhere is how to form the certificate. I spent over 400 minutes on the phone with MS with them trying to get the cert to work. They finally fixed it somehow, but in my 2nd Lync deployment for a customer repeating their steps didn't work. I have no idea what sort of dark magic they used to make our first deployment work, but I was dead set to figure it out. Shut up and tell me how to even certificate you say? PREPARE YOURSELF FOR THE KNOWLEDGE DROP!
Assuming you've got your CA setup on a domain controller or something and all that jazz is working (I'm not even going to get into that), hop on your exchange server and bust open that Exchange Management Shell. Run the following command with the modifications listed below it:
[PS] C:\Windows\system32>New-ExchangeCertificate -Server EXCHANGESERVER -GenerateRequest -FriendlyName UM-Certificate -PrivateKeyExportable $true -SubjectName "c=US, s=YourState, l=YourCity, o=Company Name, ou=IT, cn=exchangeserver.domain.local" –RequestFile "\\CASERVER\share\Exch_UM_ps.cer"
Substitute EXCHANGESERVER with your exchange server name
Substitute US with your 2 character country name
Substitute YourState/YourCity with your state and city names
Substitute Company Name with your company name
Substitute exchangeserver.domain.local with your exchange server's .local FQDN (exchange2013.mordor.local for instance)
Substitute the \\CASERVER\share\ portion of the final file path with some server that you can dump a cert on. The share will need to allow "Exchange Trusted Subsystem" full permissions.
Once you run the command, browse to that share and open the .cer file with notepad. Copy the big mess of text and browse to your CA's website (http://caserver/certsrv/).
Click "Request a Certificate"
Click "advanced certificate request"
Click "Submit a certificate request by using a base-64" blah blah blah
Paste that big nasty wad of text into the "Saved Request" box
Change Certificate Template to "Web Server"
Click that submit button so flipping hard
Download dat cert
Double click the cert (while still on the exchange server) and click install cert. Bust open your Exchange Admin Center and flipping click Servers on the left side. Go to the Certificates thing at the top. UM-Certificate should show up in there. Click on that guy and click the pencil looking deal to edit it. Click services on the side like it ain't no thang and place flipping checkmarks beside "Microsoft Exchange Unified Messaging" and "Unified Messaging Call Router". Click save. Close all that jank and open Services, restart Microsoft Exchange UM and Microsoft Exchange UM Call router services.
Now test voicemail and junk. That bzns should be working harder than an ill tempered IT man on a monster-fueled video game binge.