So after some research I decided to stick with the OSM metadata. I found the Overpass API, which is basically a query language, which I managed to understand reading this:
http://wiki.openstreetmap.org/wiki/Overpass_API/Overpass_QL
and testing it here
http://overpass-api.de/query_form.html
I ended up with this query:
way
["highway"~"motorway|trunk|primary|secondary|tertiary|unclassified|residential|service|motorway_link|trunk_link|primary_link|secondary_link|tertiary_link|living_street|pedestrian|bus_guideway|raceway|road"]
({bbox});
(._;>;);
out;
This finds all the roads I considered public using a highway filter within my bounding box. Then takes those ways and loads their nodes - (._;>;); - such an obvious statement, isn't it!
This gives me the necessary metadata to use for filtering. Now I can construct geometries and intersect with my tracks using .Net Topology Suite
https://github.com/NetTopologySuite/NetTopologySuite