We had the same issue with an Windows Server 2016 and 2019 RDS environment. We also experience problems that the start menu randomly didn’t open on multiple terminals servers. After some time we figured out it had something to do with the Windows firewall. On each terminal there where several incoming and outcoming rules created for each user that logged on to the terminal server. The rules where never removed at log off so the firewall started to get overloaded with thousands of rules.
Microsoft does have a fix so the firewall rules are removed after log off. https://support.microsoft.com/en-us/help/4490481/windows-10-update-kb4490481
Addresses an issue that slows server performance or causes the server to stop responding because of numerous Windows firewall rules. To enable this solution, use regedit to modify the following and set it to 1:
• Type: “DeleteUserAppContainersOnLogoff” (DWORD)
• Path: HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy
This fix does work but I first had to manually remove all the firewall rules from each terminal server. Because some servers couldn’t open the firewall settings anymore we’ve found a script that removed the firewall rules and notifications from the register.
But after the script removed "HKLM:\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Notifications" we started to see al lot of tasks being queued which will never run. This had nothing to do with the sysprep issues I have read about.
We took another fresh 2019 server and exported the "HKLM:\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Notifications" key (and sub keys) and imported it to one of the affected terminals. After a reboot the scheduled tasks where up an running again and the start-menu was still working fine.