I wonder if part of the problem is the lack of color in these examples? I remember Microsoft Office 97 and 2000, which had icons in their menus (albeit only for a few actions, not for every action). However, those icons were colored and appeared visually distinct from each other.
Yesterday I booted my 350MHz Power Mac G4 for the first time in 13 years. I booted into Mac OS 9.2.2. I remember the Apple menu having icons for every item. Once again, though, every icon was in color.
Isn't the Apple Menu basically a start menu though?
Written words don't have colour, and you can parse those with ease.
And the loss of skeuoumorphism. As much as designers chide it, skeuoumorphic interfaces are, when done well, a massive improvement in usability compared to flat/monochrome ones, both for new and experienced users.
It's not really visual "clutter", the shadows / pseudo-3d elements help the brain distinguish between different types of elements, providing contextual information.