From what I have seen, much of the research in this area is currently comes from GIS (Geographic Information Systems) research, as they run searches over very large datasets. Most hierarchical search strategies are non optimal and are focused on very large data sets.

I don't know if the items they are optimizing for match what you would be optimizing for. For instance, there is a fair amount out there about optimizing storage of the graph, to avoid disk reads; this may be applicable to cache issues for game developers though.

Here are a few permutations which gave me hits on google:

gis hierarchical path
hierarchical pathfinding pdf
hierarchical wayfinding

Yun-Wu Huang has published many papers that may be of interest (http://citeseer.ist.psu.edu/cis?q=Yun-Wu+Huang)

If you aren't familar with the website citeseer (citeseer.ist.psu.edu), you may want to check it out as well. It has a huge collection of papers you can download.

One issue I hit when I started to look in to all of this is the difference between clustering and partitioning. Clustering tends to mean 'transforming a graph for human interpretation', and partitioning means 'transforming a graph based on an algorithm'. This isn't always the case, but it was a general pattern I hit at times. Be prepared to spend some time reviewing graph theory.

If you find anything that looks helpful, would you mind posting a link to it here? I am collecting papers on this topic as well.