I'm not pretty sure, if this is a "OSM problem", as we can only map, what we see and add given tags. - Or, how other maps solve the issue?
Maybe the routing software has to become smarter...
to quote imagico (http://blog.imagico.de/social-engineering-in-openstreetmap/)
"So if – as a mapper – you want to really support and encourage competent data use better ignore any assumed interests of data users and map as you as a mapper can most efficiently represent your observations on the ground in data form."
this might very well apply in this situation, so when you can better tag a sidewalk with a separate line, why not ?
m.