Later JVM's that Tomcat runs, that SSPR runs inside, and thus is a victim of the parent JVM may require a couple of things.

That the Subject Alternate Name in the cert match the name used in the request (And annoyingly case sensitively I believe).  Since eDir certs for LDAP are a piece of cake to remae and swap for LDAP (and signed by same parent so easy to swap) I would consider making a cert who SAN matches that name exactly (As well as  all the server possible names).

There are override settings you can start the Tomcat instance's JVM with but I am not certain it is the greatest idea to do that.

Are you accessing your DCs via a loadbalancer or some kind of DNS round robin?

That would explain random failures if you connect to a server that isn't the one you retrieved the certificate from.

SSPR does not support an alias or load balancer for LDAP. You must explicitly list all LDAP servers that SSPR should be connecting to.

With 4.4 there is no need to import specific server certificates anymore but just use the CA one instead.: https://www.netiq.com/documentation/self-service-password-reset-44/release-notes-sspr-44/data/release-notes-sspr-44.html#t48blnuwu0dd

Are you accessing your DCs via a loadbalancer or some kind of DNS round robin? --- no 

Tried following and it worked.

1. Re-loaded the  AD certificates  for couple of times in SSPR

2.Rebooted the Server