A* in Clojure - trickier than I expected
I'm not going to be able to do a very thorough review. The code doesn't have anything outright wrong with it, and I'll admit, I've never been able to implement a decent A* implementation. It's just not something that's ever clicked for me very well (cue a new project to fix that).

That said, there's a few minor things that can be pointed out:

(fn [_] node) can be written as (constantly node). Your use of complement suggests you like to avoid explicit functions.



You can also replace:

(map (juxt identity (fn [_] node)) cheaper)


with:

(map vector cheaper (repeat node))


I personally find the latter to be much cleaner. (map vector xs ys) zips xs and ys together into pairs. Here, I'm just zipping cheaper with an infinite list of nodes. 



#(-&gt; % graph keys)


can be replaced with:

(comp keys graph)


If, again, you want to avoid explicit functions (although that's not necessarily better).



I don't think returning "no more neighbors" is a great idea. If you need an indicator value for something like this, I'd probably define at the top something like:

(def no-neighbors ::no-neighbors)


Then return no-neighbors. You could also just use ::no-neighbors inline wherever you need it, but then you need to change it multiple places if you ever decide to change the keyword used. IDE's can help with that, but I like to just avoid the problem.



You could avoid the efficiency problem regarding neighbors if you had neighbor-f return a lazy sequence of keys. I can't off hand think of a good way to do that though.



You never use prev-node. It's good to remove dead code like that to remove bulk.



I think that's all I can really comment on. Hopefully someone else can give you a better review regarding the algorithm itself.

Good luck!