Enough to make the lists on the start submenus to become very long. People don't remember it so much because nobody uses it anymore and nobody uses it anymore because it just doesn't work. With WinME MS started hiding option that weren't used frequently, in XP and 7 MS start bringing the most frequently used options to the first page. After 7 the start menu and submenus were killed because they didn't work anymore with normal computer usage.
Historically, Windows didn't really have the grouping by application type that GNOME did - any grouping in the Start Menu was down to whatever folders any given app would create when installed. It did have some standard folders like "Accessories", but I don't recall any third-party app using those. The common practice was (and still is) for every app to create its own top-level folder, then put its shortcuts underneath. So it ended up as a linear list of apps, which of course doesn't scale well - but it's also not how GNOME did it.
I will also note that, 1) the start menu is still very much there in Win11, including folders, and 2) the fact that hacks like Start8 exist and sell enough copies to be profitable indicates that quite a lot of users do prefer it to the newer arrangements.
I don't recall ever seeing that in GNOME 2. In MATE, if I remember correctly, you need to install a different system menu widget for the taskbar (although some distros do it out of the box): https://packages.debian.org/buster/mate-menu
Yes, on Linux (both KDE and Gnome), the typical menu arrangement was to group applications by category. So if you want a photo-editing program or a drawing program, you'd open up the applications menu and look for "Graphics", which makes sense.
On Windows, you just have to know which applications are already installed, and then you open the application menu and look for "Adobe" or "Corel" or whatever vendors make the software you're hoping to find there.
One of these is much more "discoverable" than the other.
