MSFT support engineers have identified a bug with the USB tethering on Lync Phone Edition. They compared the packet traces of the PIN authentication successful TLS handshake and compared it with the failed USB tethering TLS handshake.

They observed that during PIN authentication, the Lync phone connects to the Lync server over port 80 to download the intermediary certificate whereas during USB authentication, the phone skips that step and immediately attempts to handshake on SSL 443. The problem is the handshake fails because the phone does not yet have the intermediate certificate.

Quick conceptual background: A certificate chain is commonly composed of a Root certificate, followed by an intermediate certificate, and finally the issued certificate.

So in summary, there is a bug in the Lync Phone Edition firmware that is preventing the intermediate cert download from occurring during the USB tethering.

This is why the USB tethering works successfully following the PIN authentication, because during the PIN authentication, it successfully downloads the intermediate certificate.

MSFT is going to document this issue into a Knowledge Base Article and then inform the product engineering team. There is no guarantee that the product group will fix this behavior since there is a reasonable work-around to use PIN authentication.

Another potential fix is to find a different certificate authority that may skip the intermediate authority and issue device certs directly from the root authorities that come pre-loaded on each phone as described at the bottom of (this) MS Technet article.

This is not very practical because you would first have to purchase the certificate from Comodo, Verisign, Entrust, etc to find out whether they issue certs directly from the root and skip the intermediate. Also, it is highly unlikely that we would find a CA provider that does not have an intermediate authority because best practice is to mask/shield the root from direct contact by issuing certs from the intermediate rather than the root.