Ich habe zum ersten Mal das Routing mit AndNav2 (http://www.andnav.org/) ausprobiert und gleich Probleme gehabt. Die Ursache war eine fehlende Verbindung zwischen zwei Straßen; die Knoten waren zwar nah bei einander, aber nicht verbunden. Ich hab dann rausgefunden, dass es ein Skript gibt, das solche Stellen automatisch findet. Die Ergebnisse für Deutschland gibt es hier:
http://osm.flacus.de/Waycheck/
Nachdem ich jetzt ein paar Stunden drangesessen habe, sollten einige Probleme im Saarland behoben sein.