I've used navit routing on the N900, for quite long routes also, i.e. 100km, so not super far, but still enough, and it wasn't as bad as you'd expect. The only catch was that there was no `calculating route' or something, message displayed, so it took, I'd say 4 secs, and for that period, you thought the gadget froze.

But it can be realistically used in practice. Don't know about navit's routing libs for interfacing too, and there is the problem with OSM data you mention.

Anyhow, navit's solution, is off-the-n900 conversion and then just download to N900, that's not bad. I mean, you don't need to keep updating your maps every second.

The commercial vendors only do it let's say twice a year, and no big fuss, plus you can do it when you desire, on the PC...