downloading nearly 400kb of data at every level change does not sound good to me
That's 390k of RAW data. It will compress down pretty dramatically.

This is where things get tricky. No single pathfinding solution is perfect. This one is a direct compromise of memory in exchange for CPU performance. But if you were to use this along with some others, you have a very real and workable solution. This technique is not actually designed to be used on a grid at all, it's actually designed for open terrain where the number of nodes can be dramatically reduced. I put it on a grid to just show what can be done. I have another example where you simply place nodes and it can tell you the fastest route between them.

So if you have a nice pretty game (tile-based or otherwise) you could use this technique to help people find their way down long twisty halls and between rooms, and you could use robust pathfinding to get you to the nearest node. Make sense? This is what a lot of commercial games do. So from room to room could use this (long paths that would rape most pathfinders) then use the real-time pathfinders like A*, etc. for the intra-room stuff.