Ich möchte hier nochmal meine Erkenntnis für andere festhalten und zusammenfassen:
0. Grundlegendes Setup
Die 3CX Anlage ist auf einer VM in der Hetzner Cloud installiert und öffentlich erreichbar. Sämtliche Nutzer sind über die Microsoft 365 Integration im System angelegt mit Single-Sign-On. Aktuell ist von 3CX Version 20, Update 2 installiert. Bei allen Benutzern ist der Haken raus bei "Blockieren von remote Nicht-Tunnel-Verbindungen". Nur so ist es möglich, dass sich die Gigaset Telefone verbinden:
1. Anlegen des Telefons
Für fast alles Benutzer habe ich über "Nutzer bearbeiten" => "IP-Telefon" => "Hinzufügen" ein generisches IP-Telefon hinzugefügt, da wir noch sehr viele alte Gigaset C610 haben, die sich nicht über einfaches "Auto-Provisionieren" einbinden lassen.

3CX erzeugt anschließend Zugangsdaten für das Telefon:

Mit den angezeigten Zugangsdaten wurde das Gigaset Telefon konfiguriert (kein STUN, kein Proxy etc.). Einfach direkt den Hostnamen, die Auth-ID und das Passwort eingeben und speichern. Das Telefon verbindet sich ohne VPN, Proxy etc. direkt mit der Cloud-Telefonanlage (Telefon steht z.B. beim Benutzer zu Hause)
2. Löschen eines Telefons
Wenn man bei dem Telefon des Benutzers auf "Löschen" klickt, werden die angezeigten Zugangsdaten nicht ungültig. Das Telefon bleibt weiterhin verbunden und telefoniert mit der Nebenstellennummer des Benutzers.
Das ist immer noch in meinen Augen ein schwerer Fehler der 3CX Anlage.
Die vorgeschlagene Lösung von
bitn2, das Passwort zu ändern funktioniert leider nicht. Das Feld lässt sich in dieser Oberfläche nicht bearbeiten.
Was man aber bearbeiten kann, ist die Auth-ID.
Ich empfehle also, die Auth-ID durch einen langen Text zu ersetzen und zu speichern. Das Telefon ist dann nicht mehr verbunden. Anschließend habe ich das Telefon gelöscht.
3. Noch eine Erkenntnis
Erstellt man wie oben beschrieben Zugangsdaten für ein Telefon, löscht diese und erstellt nochmal neue Zugangsdaten, sind die zuerst erstellten Zugangsdaten weiterhin noch gültig. Ich weiß nicht wie lange diese gültig sind, aber mindestens 24 Stunden (so lange läuft jetzt mein Experiment).
Ich kann die Erklärung mit der Nebenstelle von bitn2 auch nicht nachvollziehen. Das Telefon gehört zwar zu dem Benutzer (mit z.B. Nebenstellennummer 15), aber die Zugangsdaten des Telefons haben mit den Zugangsdaten des Benutzers überhaupt nichts zu tun. Ich kann auch schlecht den Benutzer mitteilen, dass er sein Microsoft Passwort ändern soll, weil ich ein Telefon austausche? Im übrigen habe ich mittlerweile selbst das versucht und die gelöschten IP-Telefon Zugangsdaten bleiben weiterhin gültig.
Ich hoffe jemand bei 3CX liest das hier mit und schaut sich das auch an. Das geht einfach gar nicht und wenn ich das vorher gewusst hätte, wären wir definitiv nicht weg von der vorherigen Anlage.