The problem is in the code that does in evict for LRU/LU/FIFO caches:
(let [v (get cache key :miss)]
if (= v :miss) ....))
In the case that v exists and is a java object, the = op will result in a call to v.equals for that specific class. That method is arbitrary and might be expensive. An example case is Matrix4d from vecmath https://github.com/hharrison/vecmath/blob/master/src/javax/vecmath/Matrix4d.java that would throw and catch exceptions.
Proposal: replace check with (contains? cache key) where possible and where not, reverse the args so it is (= :miss v).