The thing about copy-on-write is that it's only a good solution when writes are infrequent. My sense is that Clojure largely deals with this by simply not targeting business domains where frequent writes to mutable data structures are particularly necessary.

Which hints at my own opinion on how to deal with this Gordian knot: just acknowledge that there is no universally best programming paradigm. Some problems are, as a practical matter, best modeled in an imperative manner. That's fine. And I don't think it should be personally threatening to us fans of functional programming. John Backus openly discussed it in the paper where he originally proposed the paradigm, and I personally prefer, for moral reasons, his suggestion for how to solve it. In a world where everyone's trying to build the best spork, I think I'd rather have one good spoon and one good fork.