I just tried to use GPSMapEdit to test routing in the danish part of the OSM map, and there is along way ahead of us.
So for the long winter evenings without enough traces to work on, I think I am going to verify the routing of the existing ways with GPSMapEdit.
What I do is like this:
Use wget http://download.geofabrik.de/osm/europe/denmark.osm.bz2 to get the proper data.
Use java -Xmx512M -jar "mkgmap-r630\mkgmap.jar" to create a proper IMG file
Use GPSMapEdit from http://www.geopainting.com/en/ to build and verify routing
First thing to do in GPSMapEdit is to build the Routing list with
"Tools->Genrate Routing Graph -> Using Coinciding Nodes of Polylines"
And finally the "Test Routing Graph".
This reveals a lot of places where ways seems to be connected but there is a little gap. It also has revealed several places of roads with incorrect oneway direction and even missing oneway dairections.