I suspect that certain combinations of hardware, software and Shell Extensions are to blame.
IMO, it's just like how some people state that certain programs always crash and yet other people never experience any problems.
It may happen more often than it is reported because the user has to notice the icon is missing.
On my PC, I generally only see this in the Start Menu and it is usually when I am searching for a program that I don't use on a regular basis, or that I normally start some other way (like from the Taskbar).
For example, occasionally I have noticed that the Firefox icon in the Start Menu is broken, but normally I run Firefox via a batch file that is pinned to my Taskbar.