I found the solution:
About two years ago we got new workstations. The major part of the configuration was copied from the old workstations.
/etc/ldap/ldap.conf was copied, too.
The files specified by TLS_CERT and TLS_KEY were copied to the new workstations, but the file for TLS_CACERT was forgotten.
After copying the last file ldapsearch is working. And the login problems are gone!
I found the solution:
About two years ago we got new workstations. The major part of the configuration was copied from the old workstations.
/etc/ldap/ldap.conf was copied, too.
The files specified by TLS_CERT and TLS_KEY were copied to the new workstations, but the file for TLS_CACERT was forgotten.
After copying the last file ldapsearch is working. And the login problems are gone!
There should be a warning about a missing file.