I had upgraded to Win10Pro from Win7 once, and rolled back/re-upgraded in order to recover my start menu once only to have it break again after rebooting.

After spending several hours and attempting different fixes (DISM etc.) to recover my Start menu, the Microsoft start menu troubleshooting utility told me I was effectively SOL because Cortana and some other necessary applications were not properly installed. Unrelated, I stated to receive an error for a popular game (Overwatch, error: 0xE0070150) which is sometimes resolved by installing graphics card drivers. Upon reinstalling Nvidia drivers 368.81 my start menu returned and the game also worked (no reboot necessary).

I still lose my start menu every time my system reboots, but my workaround at present is to sleep-state unless rebooting is necessary and simply reinstall the GPU drivers every time. I hope the anniversary update fixes this issue (maybe even the reason why they are making the spy-queen Cortana mandatory is to avoid whatever under-the-hood conflict is robbing people of their start menus).

I haven't come across a connection between GPU drivers and Start menu issues when I was trying to fix things -- can anyone here help me figure out why I need to reinstall them every time after rebooting?

I can provide a DxDiag dump etc., I just don't want to flood with too much information.