I cannot reproduce the problem with valhalla on OSM, can you?  Use the openstreetmap.org website, specify from / to points and specify the valhalla router.  It does the expected route.

You probably have incorrect data or non-OSM data is the only thing I can think of.