The strongest case for using protocols is for working with existing types. This usually means other people's code, java types etc. This is unique functionality to clojure and is probably its most important motivation. This also means that reloading doesn't usually cause issues, since the types aren't changing.
Still, Protocols, and even multimethods have limitations. Which means, for any given problem, make sure you start from first principles and not just immediately turn one or the other. You have full functional programming to work for you.
For example, I defined my own version of local multimethods, which are immutable. This means you can extend to different dispatch values differently in different contexts very easily. Multimethods are basically global variables and also have reloading problems. Since local-multi-fns are defined by functions in hash-maps, you can merge, add, remove as you please, and reloading is managed by you. You can use atoms for example, and atoms can help with recursive local-multi-fns (still just one way to do it).
Details of the idea is
A simplified definition is like the following:
(defn very-simple-multi-fn [implementations dispatch-fn]
(with-meta (fn [& args] (apply (implementations (dispatch-fn args)) args)) {::very-simple-multi-fn {:implementations implementations}}))
(let [x (very-simple-multi-fn {\a (fn [& args] ...) \b (fn [& args] ...)} (fn [args] ...))]
(x ...)
(let [y (very-simple-multi-fn (-> x meta ::very-simple-mulfi-fn :implementations (merge {\c ... \a ...})) new-dispatch-fn)]
(y ...)))
I recommend just writing your own version of this and decide how much flexibility you need.