Two additional ideas to incorporate:

1. If you have a long upgrade to make (say, from 2.6 to 3.1), the easiest solution is to do it by stepping from LTS release to LTS release, clearing deprecations as you go. This strategy works because those upgrade paths tend to be well-tested ones by lots of other people before you, and also because we try hard not to break even private APIs that we know are used by popular addons without first showing a deprecation warning through an LTS cycle.
2. As long as you aren’t crossing a major release boundary, it’s fine not to try to clear all deprecations immediately. One of the best ways to do this is to use https://github.com/mixonic/ember-cli-deprecation-workflow to mark specific deprecation messages as either “silence”, “log”, or “throw”, so you can make slow and steady progress while preventing backsliding.