I just came across this same issue on our Windows 2016 RDS Host server we have had running for many years. The reg entries under the \HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\FirewallRules section and \HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\RestrictedServices\configurable\system were plentyful and yes it took about 1/2 hour to load the entries to the screen and another 20 minutes to delete all of these entries. However, yes it immediately corrected the START MENU and Search menu.... wow. thank you for this.... I also, had the same issue on 2 Windows 10 pc work stations with the same exact issue that this same resolution corrected our 2 Windows 10 pro and Windows 10 Enterprise pc's. So, not sure if this is a Windows bug or update issue....however, the commonality across these machines other than Windows 10/Windows 2016 which, we know are similar OS's. However, all of them were running Symantec Endpoint protection which, overrides the Windows Firewall and maybe this is a Symantec A/V issue?
Are any of you other users, with this issue, running Symantec Corp Endpoint on your servers that could be leaking memory causing these multitude of Firewall rules to be created in the registry or some Symantec A/V updates???
Additional notes.... I deleted all of these entries and refreshed and none of them re-appeared. However, if I log off and log back on again. they start re-appearing again in both registry locations. So, it seems during login these get recreated. So, as a test I have de-installed Symantec, rebooted, re-logged back onto the server and reviewed the registry entries. This then, required the Windows firewall to be turned off since, no RDP rules now existed to connect to the RDP Host session but, of course I had to console into this VMWare server.
However, after removing Symantec, rebooting, deleting registry entries, again, rebooting....they still keep coming back. Even with the firewall OFF and Symantec A/V removed.....
@Björn Braun Resolution definitely so, I did also add the suggested work around of the below to prevent this from happening
Set DWORD "DeleteUserAppContainersOnLogoff = 1