GNOME Shell (both master and the overview-relayout branch) present the list of launchable applications to us as a large, non-hierarchical, immediately searchable list. We can hit the logo key and start typing a few letters and immediately find what we're looking for. KDE has it. Windows Vista and 7 have it. OS X has it (via Spotlight). And now we have it.
On Debian this is a problem because menu and menu-xdg convert an ancient, Debian, unified menu system that predates the existence of the cross-desktop XDG menu specs in to XDG menus and stores them in /var/lib/menu-xdg
duplicating everything that's already in the standard /usr/share/applications
. This wasn't really a problem because all the duplication was crammed in to an easily avoidable "Debian" menu. The idea was that you'd get the same Debian menu in all desktops. Unfortunately, this isn't getting killed off fast enough. However, we can change it for our own systems.
sudo update-menus --remove
sudo apt-get purge menu
The first step is required because /var/lib/menu-xdg
is not considered configuration and therefore the contents of this directory are not removed on package removal. It is necessary to the remove the menu package to prevent package installation from triggering the recreation of these menus via the dpkg triggers mechanism.

Comments
Gnome and KDE in particular seem not to show you all the software, but even for the software they do, I find it easier sometimes to locate it on the Debian menu.
Later, Seeker
In addition, you should purge both menu and menu-xdg instead of doing sudo update-menus --remove.
A lot of the times I don't know the name of the applications I am looking for. Like I want to find the font settings or something like that. It's very difficult to figure the magic words that will give me a icon to launch. Or if I want to go do something like search for network shares... what is the search term that is suppose to bring that up? And how would a person using the desktop for the first time know this?
Also the search does not allow for discoverability very easily. Like if I am bored and want a video game there is no easy way to find all the games that I have installed.
Search is very cool, especially for things i use frequently, but it's no substitute for application menu. It is a terrific addition to it though.
The relayout-branch is midway through implementation and is somewhat close at this point but it should be very close to that mockup when finished.
Why not keep applications sorted in a vertical, hierarchical menu? It is much easier to find them in a single direction than to have to look in two dimensions. It’s the reason why the list view in Nautilus is preferred over the icon view.
In all cases, the Debian menu is explicitly disabled by default, with NoDisplay=true set in Debian.directory. It is therefore a bug in GNOME Shell to show the entries that come from this menu.