Clojure doesn't have to do this because it was designed to allow separate compilation as much as possible[1], and because it hardly ever changes binary representation in backwards-incompatible ways. Protocols and multimethods are indeed handled at the call-site, but in such a way that a change to the protocol/multimethods don't require re-compilation of the callsite[2]. Similarly, Kotlin, a statically typed language distributed in binary, is also designed to allow separate compilation as much as possible[3]. If a feature would break that property (e.g. require re-compilation of a callsite when an implementation changes at the call target), that feature simply isn't added to the language.
This is a design that admits that extra-linguistic features (like separate compilation) are as important as linguistic abstractions (sometimes more important).
BTW, separate compilation isn't only a concern with Java class files. Object file linking also places limits on how languages can implement abstractions yet still support separate compilation. Some languages place less emphasis on this than others.
[1]: In fact, as a Lisp, Clojure's unit of (separate) compilation isn't even the file but the top-level expression. No top-level expression should require re-compilation if anything else changes.
[2]: The implementation of protocols: https://github.com/clojure/clojure/blob/master/src/clj/cloju...
[3]: Even Java doesn't support 100% separate compilation. There are rare cases where changes to one class requires recompilation of another.