A new install of Lync and Exchange. Enabled enterprise voice and Unified Messaging. Useres never get missed call notifications in their mailbox. On the exchange server there where several entries in the eventviewer complaining about smtp and voice mail files.

Solution to this is to verify that the receive connector that exchange itself uses is enabled With “Exchange Server authentication”. Most common issue is that som admin has created a relay connector and defined a IP subnet in the “network” tab, and this IP network contains the IP address of the exchange server. You can verify witch connector that is used by Exchange by examining the smtp log file.

Update: 

Also verify that the CA trust list is not to large as i pointed out in my Lync post : https://www.vatland.no/post.aspx?id=24303d6b-a29e-432c-b448-3dac2779bd14