One downside to the ribbons that I see is that they somehow inverted the hierarchy between menus and toolbar buttons: Previously, menus were the slow but predictable way to find a command, and both toolbar buttons and keyboard shortcuts were just that - shortcuts. Menus were a sort of "ground truth" which commands existed. They also had a standard way to be navigable through the keyboard: You can press alt and then simply use the cursor keys.

With ribbons, the menus were gone and the toolbar buttons became the "ground truth", but in a much more haphazard way.

Fuzzy command search goes a bit back to menus, but as you say in a way that's much less guaranteed to be stable.