I am not really fan of third party solutions, because you alvays get to the point where something can't be done.
I like my solution for now. I will try to precalculate the numbers, so there will be no limit on the size.
Yesterday daily dumps of categories was set up. I am working on automated update, and then I will suggest to Chris to add a link to Category Navigator on all category pages.
I might also extend parent categories on the navigator.