Notices

IANAP, but I suspect an application that generated usable routes would (along with its database) be more than the N800 could handle.

Nah, I doubt that. The 780 I have uses a Samsung processor @300-400 mHz and it does routes on the fly. The NITs use a superior 400mhz ARM chip, so I see no reason why a NIT couldn't do the same thing.

Silly. The reason maemo mapper cannot do routes is that it doesn't know where the roads are. The maps are just tiled bitmaps.
It would have to do image recognition to build a database of road locations and place names. Fun, eh?
My Symbian phone can calculate routes easily, with a much weaker CPU.

Well, alignment and parsing wouldn't be all that hard. All that the other map programs with raster images do is look at where you are, where you're going, and then look at each image within the database between those two points, look for roads by identifying patterns within the tiles, and then plot the route accordingly.