We're not using Neo4j because of other unrelated constraints that have led us to write our own graph data store. Kenny's work implemented the "rule paralleling queries" approach you mention.
I'm not sure about Prolog, but Java's Antlr library was really easy to use. Writing the parser+lexer infrastructure only took a few days. It wasn't quite as clean as using Antlr in a language like SML, but for implementing a parser in Java it was pretty great.
I may move to Common Lisp or Clojure for writing DSLs, but I am pretty happy with my early experience with Treetop. The one downside, especially compared to Antlr which has a couple of books out there, is that the Treetop documentation had me more than once scratching my head and hacking rather than looking up a relevant reference.
I think parsing expression grammars and packrat parsing in general is going to explode the DSL dev scene . . .
There is also a Neo4j Heroku Add On (http://addons.heroku.com/neo4j) that is currently free for developers.
also, i wonder if life would have been easier if the implementation had used prolog? not only is it famously nice for supporting dsls (don't ask me how - i've never done it, but you can imagine that parsing is pretty easy, since you get backtracking "for free"), but it might provide much of the scaffolding needed to evaluate queries.