Ich habe das Problem mittlerweile behoben - wenn auch etwas anders: Ich habe mir ein alternatives Gateway auf Basis eines programmierbaren CC2531 USB Sticks erstellt. Auf diesen wird eine Zigbee Firmware geflashed, so dass er als Xiaomi Gateway fungiert (und ganz nebenbei auch noch als Gateway für Hue, Tradfri und weitere, beliebige Zigbee-Derivate). Weiterer angenehmer Nebeneffekt: Die Kommunikation geht nicht mehr über die Xiaomi-Server sondern alles bleibt in der Wohnung.
Wer keine Home-Automation Zentrale, die MQTT unterstützt im Einsatz hat, sondern lediglich das Xiaomi Gateway als einzige Zentrale verwendet und als Interface dazu die Xiaomi-Software, für den ist diese Lösung nicht geeignet.
Der erste Gateway Stick auf CC2531-Basis kostet ungefähr genauso viel wie das Original-Gateway von Xiaomi, da man noch einen Debugger zum Neuflashen und das Zugehörige Anschlusskabel dazubestellen muss.
Ab dem zweiten Gateway (oder wenn man jemanden in der Nähe hat, der den Debugger nebst Kabel besitzt) kostet einen das alternative Gateway ungefähr 6Euro (bei AliExpress, Stand 22.08.2018)
Nachdem der CC2531 Stick innerhalb von 10 Minuten mit neuer Firmware bespielt war, konnte ich alle Xiaomi-Sensoren, problemlos beim ersten Versuch pairen. Mein oben geschildertes Problem lag also definitiv am Gateway.
Einziger Fallstrick: Beim Anlernen einiger Xiaomi Devices (bei mir: die runden Fensterkontakte) muss man relativ nahe am Gateway sein (10 cm) und alle zwei Sekunden auf den Pairing-Knopf drücken. Also am besten bei allen Sensoren so vorgehen Nachdem die Sensoren angelernt sind, kommunizieren sie bei mir problemlos über eine Distanz von 10m durch 2 massive und eine Hohlbauwand)
Bisher läuft das Ganze bei mir seit drei Wochen absolut stabil und zuverlässig mit allen Xiaomi Komponenten. Hue, Tradfri und wie sie alle heißen mögen, konnte ich in Ermangelung von Geräten nicht testen, laut der Berichte von anderen Benutzern scheint das aber ebenfalls problemlos zu funktionieren. So sieht das Ganze bei mir in ioBroker eingebunden aus:
Hier die Seite zum Projekt: https://github.com/Koenkk/zigbee2mqtt
Dort findet man auch eine Liste mit allen unterstützten Devices, eine Schritt-Für-Schritt-Anleitung für den Flashvorgang und die Einbindung in diverse Home Automation Systeme, sowie eine Anleitung, wie man vorgehen sollte, um noch nicht bekannte ZigBee Devices zu melden, so dass diese vom System unterstützt werden.
Fazit: Nach langer Zeit kann ich mein Xiaomi-System endlich so ins Heimnetz einbinden, wie ich es wollte. Neben der Unterstützung aller Sensoren, bin ich zudem noch unabhängig von der Xiaomi-Cloud und habe nebenbei ein universelles Zigbee-Gateway erhalten und das zu einem unschlagbar günstigen Preis.