Das ist höchst merkwürdig – oder kann es daran liegen, dass du für dein LAN und den Server darin keinen extern auflösbaren FQDN hast aber ich schon?
Jedenfalls ist der Fortschritt im Moment überaus zäh und für mich undurchsichtig zu deuten, wo es klemmt. Ich denke aber, dass ich das Problem soeben gelöst habe (bzw hatte @mdt bereits alle notwendigen Fakten aufgeschrieben; ich musste sie „nur“ nochmal für mich ordnen. Danke nochmal für die zahlreichen Tipps!!).
Also es ist so: Wenn ich auf dem Server selbst das hier mache:
ldapsearch -b "ou=default-school,ou=SCHOOLS,dc=linuxmuster,dc=meine-schule,dc=de" -H ldaps://server.linuxmuster.meine-schule.de:636 -x -D global-binduser@linuxmuster.meine-schule.de -w geheimesPasswort givenName=Michael
klappt das alles; ganz egal, ob ich da ldap:// mit Port 389 oder 3268 oder aber ldaps:// mit Port 636 oder 3269 eingebe.
Das gleiche auf einem Client lief aber immer nur dann, wenn ich Port 389 oder 3268 verwendet habe. (Es ist dabei für mich immernoch unklar, wie so eine Verbindung in Kombination mit Kerberos aussieht?!? Ist das unverschlüsselt oder nicht?).
Immer, wenn ich von einem anderen Client (im Servernetz) die Ports 636 oder 3269 verwendet habe, gab es einen Zertifikatsfehler à la:
Can't contact LDAP server (-1) (mit der Option -d1 wird das genauer aufgeschlüsselt – dann steht da, dass es ein TLS-Fehler ist!)
Nun habe ich mir das Server-Zertifikat mit dem Befehl
echo -n | openssl s_client -CApath /etc/ssl/certs/ -connect server.linuxmuster.meine-schule.de:636
auf den Client kopiert und dann den Befehl nochmal abgesetzt mit einem vorangestellten:
LDAPTLS_CACERT=./mein-server-zertifikat.crt ldapsearch -b "ou=default-school ....
Das war der entscheidende Hinweis, dann damt lief es plötzlich. @mdt hatte also die ganze Zeit völlig Recht: Das Server-Zertifikat war dem Client nicht bekannt.
Die richtige Vorgehensweise, wie man es dem Client bekannt macht, habe ich für Ubuntu dann hier gefunden:
For everything to work and not only your browser, you need to add that CA certificate to the system's trusted CA repository.
In ubuntu:
* Go to /usr/local/share/ca-certificates/
* Create a new folder, i.e. "sudo mkdir school"
* Copy the .crt file into the school folder
* Make sure the permissions are OK (755 for the folder, 644 for the file)
* Run "sudo update-ca-certificates"
Danach lief der ldapseach-Befehl dann auch ohne das vorangestellte LDAPTLS_CACERT= endlich erfolgreich auf allen Ports; also auch endlich auf Port 636 und 3269 mit ldaps://
Ob moodle nun auch den Kontakt zum Server aufnimmt, teste ich aber heute nicht mehr … will das kleine Erfolgserlebnis nicht sofort wieder zunichte machen 
Also dann – diese Vorgehensweise betrifft sicher noch andere, die ihrem Server einen FQDN spendiert haben und sich über Zertifikatsmeldungen (die man ggf auf den ersten Blick nicht als solche identifiziert…?!) wundern. Ich ändere den Betreff wieder zu (HowTo) und markiere es (vorerst?) als gelöst.
Schöne Grüße,
Michael
P.S.: die Option LDAPVerifyServerCert Off habe ich im apache2 nun natürlich auch wieder deaktiviert! 
Das gilt nicht allein für Ubuntu sondern für Debian und alle Debian-Derivate…
