That's certainly an interesting idea. The subzone portion sound similar to the "Memory Efficient Pathfinding" paper Impaler linked to earlier.
I do have a few criticisms of your method:
Any given path through one zone or sub-zone to a neighboring zone or sub-zone on the same z-level will cost approximately the same **.
This isn't really true. The path length through one of your 3x3 zones could be as little as 1, or as much as 5. This means that the path found can be more than twice the optimal path length. Additionally, I don't think your method supports non-uniform path costs.
Also, you're only reducing the graph by a factor of 3. The overhead from keeping track of the new abstract graph (and its subgraphs) is likely to be larger than any gains you have from abstraction. I don't see a way to easily increase the amount of abstraction, so I'm not sure we can solve this without significant changes.
I was hoping for criticism.
It is an idea, not sure about interesting but it is an idea. I haven't read that paper, yet, I will try to in the near future. I may have to just break down and write the code to test it so I can get it out of my head. At the least it will allow me to do something somewhat more productive compared to my more recent endeavors. Besides, it should be good for a few laughs if I ever finish it and make it public, so that is a bonus.
I did note that the assumption isn't always true(see the "**" note). My argument for the assumption is that exceptions would generally be rare and relatively minor. Generally not more than a difference of a few tiles in the whole path when the exception happens. It is a potentially unruly assumption, off hand I can think of one case especially. However, I think it is too important for the abstraction to work to do without it.
I think non-uniform pathcosts could be supported but would have to be generalized(so it wouldn't be exact to the tile) in a similar fashion to the zone/tile connection abstraction between hierarchy levels. In fact, it could be used to allow a user to optimize the most glaring exceptions.
I was thinking that layering the abstracting by 3x3 for each level(suppose 3 or 4 levels?) of a hierarchy. The memory overhead would be higher but it might significantly reduce the CPU and memory cost during the actual pathing. If you are feeling that it would merely balloon memory cost without noticeably reducing execution cost then it is likely to be a dead end.
You didn't mention the lack of consideration for novel modes of travel, like digging/destroying obstructions, swimming, flying etc. Or was that what you meant by the non-uniform cost comment?
For novel modes of travel, I would think that there would need to be a different method all together.
I think my posts are excessively wordy without improving clarification or communicating significantly(much like the idea, HA!).