I've absolutely the same problem at our customers. If a AD userprofile (no roaming profile or something else special) was deleted through the "normal" method with deleting the key at ProfileList and the files at c:\users, the startmenu is broken after a new login.
The only thing that helped yet was to start the following command (found it at another post) at the powershell at the users context:
taskkill /F /IM explorer.exe ; taskkill /F /IM SearchApp.exe ; taskkill /F /IM SearchUI.exe; taskkill /F /IM ShellExperienceHost.exe; taskkill /F /IM StartMenuExperiencehost.exe ; Start-Sleep 2 ; cd $Env:localappdata\Packages\Microsoft.Windows.ShellExperienceHost_cw5n1h2txyewy ; Remove-Item -Recurse -Force .\TempState\ ; cd $Env:localappdata\Packages\Microsoft.Windows.StartMenuExperiencehost_cw5n1h2txyewy ; Remove-Item -Recurse -Force .\TempState\ ; Add-AppxPackage -register "C:\Windows\SystemApps\ShellExperienceHost_cw5n1h2txyewy\AppxManifest.xml" -DisableDevelopmentMode ; Add-AppxPackage -register "C:\Windows\SystemApps\Microsoft.Windows.StartMenuExperienceHost_cw5n1h2txyewy\AppxManifest.xml" -DisableDevelopmentMode ; Start-Process "explorer.exe"
This is an incredible fu**, because we just deleted about 50 profiles because of an exchange problem where the userprofiles have to be recreated.
Microsoft, give us another solution fast!