Would you consider something like Strava's aggregated GPS traces to complement how confident you are with detected roads?
For example: http://labs.strava.com/routing-errors/#250/17/-46.42546/-21.... gives a fairly strong indication that something is navigable on bicycle or foot; even if OSM hasn't mapped it yet.