Ich konnte das Problem in der Zwischenzeit lösen. Ist zwar trivial, brauchte dennoch eine Weile um es zu finden :) , deshalb hier die Lösung:
In der Terminalserver-Gruppenrichtlinie folgende Einstellung auf "Nicht konfiguriert" stellen:
Benutzerkonfiguration -> Administrative Vorlagen -> Startmenü und Taskleiste -> Standardprogrammgruppen aus dem Startmenü entfernen