I believe I have found a resolution to this issue, and it is not Jenkins related.
In my Jenkins startup script, I had a snippet that would import the current LDAP certificate into my trust store under a specific alias. However, my LDAP is on a load balancer. Once the load balancer switches me over to another LDAP instance, the certificate no longer matches. If I restarted, it re-imported the new certificate to the trust store under the same alias (overwriting the existing one). This would temporarily resolve the issue until the load balancer switched over again.
So what I have done is change my Jenkins startup script to keep track of the certificates that I have imported into the trust store. If a restart encounters a new certificate, I import it under a different alias so that it doesn't overwrite the ones I already have.
This took a couple restarts before I was able to get all the certificates (it seems we balance across 3 LDAP instances) but it appears to be working. I have now been up and running for over 24 hours without encountering this connection issue.
Michael Dicke is the author of this issue, so I don't want to close the ticket without his consent.