Mittlerweile haben wir einen Servicetechniker der Telekom vor Ort gehabt, die Lösung war auch für ihn nicht einfach zu identifizieren.

Vielleicht hilft es ja auch anderen Kunden:

Es gab ein Problem mit dem Zertifikat, da die Telefone anscheinend doch nicht Telekom gebrandet vorkonfiguriert waren (obwohl bei der Telekom gekauft).

Im Webinterface der Yealinks unter Security -> Trusted Certificates -> Only Accept Trusted Certificates -> auf "Disabled" stellen und abschließend mit "Confirm" bestätigen und neu starten.

Die Verbindung zum Server passt seitdem.