The essential condition for a map, to be used in routing, is integrity of the road network. Ideally, there should be a single strongly connected component. All edges of the road network should be accessible for routing.
Unfortunately, there are currently 1,000,000+ inaccessible edges (road segments) in OSM data. It looks that fixing them all will be hard toil.
Here is a small tool that can make this task easier:
It works in a very simple way: it displays one of the inaccessible road segments found by OSRM test, and loads it automatically into JOSM for editing.
Currently, inaccessible edges from selected areas (Poland, Finland, European part of Russia, Thailand and Japan) are suggested for fixing. In the near future it will be extended to the whole world.
The utility has user interface in English and Russian, other languages can be added if somebody helps me with translation.
Also, there is a description of the most typical situations: http://wiki.openstreetmap.org/wiki/So_that_is_what_inaccessible_road_is! and suggestions how to fix them.
Inaccessible roads in Thailand
Visualized a bit differently from OSRM Small Components layer, the components are clustered.