Non-automobile routing with mkgmap (the program used to produce Garmin .img files from OSM data) is a dark art, largely because Garmin don't really appear to have designed the eTrex's software for anything other than "big fast roads are good".
The mkgmap developers have performed pretty heroic efforts to tame it, but if you want to get cycle routing to work perfectly, you do have to invest a lot of brane cells into it... it's not just a matter of saying "compile this img with routing", which will seemingly work but won't always give the greatest routes.
As it happens, some of the mkgmap defaults seem to have been patched in by a rather obnoxious German MTB map compiler (
[mkgmap-dev] Bicycle routing improvements (reverting breakage from r1431)
is an example of his style) and I strongly suspect that the "mmm, bridleway" routing may well be something to do with that.
It's nothing to do with "routing with OSM" or "it's data is wrong" - it's an mkgmap thing. That said, I would encourage people adding bridleways to OSM to also add a surface tag ("surface=gravel", "surface=grass", "surface=mud", "surface=you're 'avin a laugh", that sort of thing), which should enable smarter routing for those of us without Mr Obnoxious German's MTB proclivities.