Nice list!
Here a few comments from me:
* there's actually fuzzy matching in the completion, but it currently works only for Clojure (compliment has it, cljs-tooling doesn't). You can't see this in CIDER, though, as we didn't make any efforts to support it in the UI.
* on the topic of losing stability - we collaborate with vim-fireplace when we're doing incompatible changes and we're obviously open to collaborate with other projects as well. Lately there haven't been that many serious changes and I'm hopeful that 1.0 is around the corner.
* as you know we're well aware of the deps issue and are looking into using either a tool like
https://github.com/benedekfazekas/mranderson or some alternative (e.g. classloader isolation to solve this). We've tried to depend only on projects which are unlikely to be used by applications (or have a stable enough API that would reduce the possibility for conflicts). At any rate, this is something that has to be solved regardless of how many projects depend on cider-nrepl.
* I don't believe nREPL lock-in is a real issue right now, as the alternative doesn't really exist. And even when it arrives there's still the problem of providing tooling support for it - obviously the built-in REPL will provide none of the functionality needed by Clojure dev tools. Much of cider-nrepl's code is not tied to nREPL at all so having something cider-nrepl and cider-whatever is definitely possible, although I'm not sure if it'll be needed in the foreseeable future.
At any rate I believe that collaboration is the key to building better Clojure tooling - most of the projects have pretty limited resources, so it doesn't make much sense to keep reinventing the wheel for every possible project (therefore our decision to leverage off-the-shelf libraries when possible instead of reimplementing everything ourselves).