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.