According to your description, this issue is related to certificate.
The root cause is after the December update, Windows Server 2012 no longer trust the certificate that is trusted before.
You need to put the intermediate CA certificates in the Intermediate Certification Authorities store. After installed successfully, the Lync Server Access Edge Service will be successfully started.
If the response is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.