Your pinned shortcuts are stored here : C:\Users\<USERNAME>\AppData\Roaming\Microsoft\Internet Explorer\Quick Launch\User Pinned\StartMenu
As long as a link exists you would expect it to still show even if the target of the shortcut has been deleted. This is normal Windows behaviour for the taskbar links and start menu links.
I would be curious to know if right clicking on the shortcut in that folder also causes issues.