Coming up late on this.
I fully understand your problem and I agree there is no easy solution.
But I’m wondering if we are not missing the point here 
- If we want to eliminate the paths explicitely forbidden for bicycles, I think it is best to add bicycle=no that bicycle=yes to all paths which are not. I expect much less work
- If we want to ensure the quality of the paths, I’d make a challenge to ask exactly that. Much more work, but highly relevant.
In the meantime, do you consider path + relevant surface=* when available as a criteria for your routing? That could be a good start and help narrow the search on paths explicitely forbidden to bicycles.