I used a program on the amiga called grale or sumit that was a monkey island style advenure maker, they did walk zones by allowing a user to draw out rectangles (player could move any where in this rectangle) then join rectanges by a single node or path, that way the player would know how to move from one rectangle to the other.
That looks like a pretty nice way of finding paths quickly, with not a lot of number crunching involved - the only problem I see with it is if you are in the far right corner of a cell and want to move to the far right corner of the next 10 pixels up, it may want to walk left first and then back right, resulting in unnatural paths.
I used a different approach: I took the original image, and painted mask of the 'walkable' area on top of it. Then analyzed the mask, and stored it in a lower resolution array of the same proportions.
(e.g. 800x600 image, 200x150 array)
If the mask was drawn, a cell was walkable, otherwise it wasn't. Then I used a standard A* pathfinder to find the most efficient way to find the destination point in the array, scaling the results to the real screen positions. The array was a smaller scale because walkmaps didn't need to be pixel-perfect, and the smaller size would be much faster to analyze.
As far as dead ends:
If there was no path to the destination point, it would take an imaginary straight line between the destination and the source point. Then jump back from the destination along that line at 10 pixel intervals or so (bigger steps on slow computers to cut down pathfinding time), and try to resolve a way from there to my character. As soon as one resolved, it would start walking from its origin to this point.
It makes the game look a lot smarter than not doing anything at all when you click on a dead end. (I guess you can do the same with your method, and move to the center point closest to your destination)