Windows 10 1703 - Start menu icons showing of apps removed from golden image

[JHBPJF]

In my golden image, I've removed applications for current user and all. First time logging in, the start menu looks like this and I can't figure out why it still thinks the icons should be there?

[HussamRabaya]

try to rebuild the index or re-index the start menu

How to Solve Windows Search Issues with an Index Rebuild