Recently I found a link to a newly released Software solution that enables you to do navigation and routing on OSM data on Windows PC or devices with WindowsMobile:
mapFactor Navigator Free
It seems to be developed by a professional czech company that normaly offers navigation as a commercial solution on TeleAtlas data.
But now they offer their navigation framework app on a special version for free, you can just download the installer and OSM map data is probably available from all over the planet.
Somebody also sais you can run it on Linux via Wine.
PS: I am not related to mapFactor company in any way!