GNOME has solved in a radical way by simplifying menus, so you need neither search nor frequent mouse/keyboard navigation.
Honestly 'even Apple does it' is a poor argument. If global menu would be a really good and generally accepted idea we'd see it implemented in GNOME and KDE (via extensions at least).