Yes, "regional" off-line routing could be a good start, as the route computation could be quite fast for a relatively small area and converting the raw OSM data for a city sized area (if the the binary API is not used) should be doable on the device without using a PC.

OK, can be interesting to see how it works with the binary data.

So we basically just show the traveler the direction from the closest node, that is also a part of a way to one of the connected nodes, that lies in the direction to the destination ? And update this periodically.

Concerning the binary format, there seems to be some sort of an alternative developing:
just stuffing the OSM data to a sqlite database
Although this article is quite old, there seems to be some progress, as there are two programs that seem to be able to do this:
osm2sqlite - some sort of a bash script
osm4routing - a python module with parts implemented in C using the boost library
Storing the data in a database could be quite handy for updating, searching, etc.

But this is not all.

There was once routing support in modRana, but then it was still called Rana and I was not yet working on it.
It seems, that the development of Rana stopped in quite an early phase, with many features not in a complete state.
When I choose Rana as a basis for a development of a navigation system, I went through the features and fixed or disabled what appeared not to be working, including off-line routing and map rendering.
So today I took a second look on that old code and, well, it seems to actually work.
Work, as in:

• it loads *.osm files and processes them to its own binary format
• it does find routes between two node ids (using the A* algorithm)
• it seems to be possible to find the nearest node id to given coordinates
• multiple route types seem to be supported (bike,car, pedestrian,horseback, etc.)
• it can even output a PNG that shows all points that are part of a way, all considered routes, the resulting route (this could be useful for debugging new routing algorithms)

I have not made any tests on the N900 yet, it is not integrated in the current routing code and handling of all the OSM data handling and conversion will have to be made more user-friendly. Therefore, this does not mean that off-line routing will be added tomorrow, but it is significantly closer than before.

Concerning map rendering, there seems to be a Python OSM renderer called Ceyx. It could be theoretically used in the future by modRana for generating map tiles on demand from OSM data.

And now back to coding, this post is already a bit too long.