Cluttered desktop
A lot of people got in the mode of creating shortcuts back in W95 and even in W3's Program Manager. I don't think those people figured out how to use the Start menu effectively, or saw any reason to. (Kinda like me and Metro.) I think many people don't differentiate between programs and data, and want everything in one place. Program installers usually add shortcuts to the desktop (along with other places), but it's easier to dump a file on the desktop than add a shortcut pointing to it to the Start Menu.
Why do you find the Taskbar superior to the Start Menu? My gripe with shortcuts on the taskbar is I quickly run out of space on it when running all the apps I use at work. Using it as a menu means space is taken up by inactive shortcuts for apps I'm not running, on the off-chance I'll want to start them. Sticking them on the Start Menu means they're not taking up Taskbar space until I want them.
