I'm posting this in the hopes it will help someone else.
So I was running 1809 with roaming profiles on a VDI solution. When a user logged in for the first time the start menu would be fine. When the user logs in the second time after the profile had already been created the start menu is all messed up. I solved this by creating the following key:
HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\Explorer
Value: SpecialRoamingOverrideAllowed
Type: REG_DWORD
Value: 1
Hope it helps.
Cheers