Yep, I spent some time playing with the macro and the macroexpand. It looks like
a) it only works if the dependent keys come *before* the keys they depend on (ie the opposite of how you'd order, say, defs)
The latter makes it pretty clear that this is accidental behavior and, as you say, shouldn't be relied on -- in particular, if you have more than about 8 keys, you spill over to a PersistentHashMap and get everything in a random order and it almost certainly fails.
The trouble is this behavior is already used by ring-middleware-format, which then fails to compile if clojure uses a different implementation for small maps.
I'm wondering if given the brittleness of this behavior we should make sure it can't be used in future versions of clojure.