I have seen this with Windows 10 LTSB 1504. Are you using LTSB version? We used the tool recommended by Microsoft to customize the start menu, which in turn would randomly break the start menu. We have since stopped customizing the start menu completely after all the issues we were having.
Are you using roaming profiles? The work around for us was to remove the users roaming profile, and have them login and create a new profile. For whatever reason, a new profile always works, even with the start menu customization.
Are you also using VMware Persona within these Pools?