Nein, das habe ich nicht explizit gemacht (mit dem anderen Wlan-Stick funktioniert ja auch alles). Habe jetzt trotzdem mal testweise eine statische MAC-Adresse erzwungen für die eigentliche Verbindung indem ich /etc/NetworkManager/conf.d/30-mac-randomization.conf angelegt habe mit folgendem Inhalt:
[device-mac-randomization]
wifi.scan-rand-mac-address=yes
[connection-mac-randomization]
ethernet.cloned-mac-address=permanent
wifi.cloned-mac-address=permanent
Leider hat das keinen Erfolg gebracht..
EDIT (20.10.2017):
Ich habe den Stick jetzt zurück zum Händler geschickt und ein Modell mit anderem Chipsatz bestellt. Ich hoffe damit löst sich das Problem von selbst.