One way to handle that is through multiple user modes. A simple case is how MS office shifted UI many times, but the keyboard shortcuts remained the same and accumulated to some extent. The key sequences are still there to navigate menus that disappeared before ribbons, or even before MS bought out the originating product. Key combos are a common thing experienced users learn almost unintentionally to speed up a workflow, but it doesn't harm the discoverability for new users or of new features.

Yes, although key combos is no magic bullet. Personally, I prefer having an "advanced" UI option that you can select when the introductory UI becomes irritating or restrictive.