OSM maps are vector maps; Roadmap and Navit are both supposed to support routing.

Ah, that's the wrong attitude , assuming you have sufficient metadata in your vector maps (like road directions, and one day perhaps speed limits) there should be no problem creating a route - admittedly it may not be ideal, but better than nothing. And quite an interesting thing to work on too IMO.