This is a problem with the Garmin map producers, not with the UK map.
Access defaults always need to be interpreted on a national level: see [the wiki][1] for a fairly comprehensive list. Bicycle and footway access on trunk roads is just one of many possible regional variations. Eliminating them all is unrealistic in the short term, and would need to be agreed across the OSM community in the long term.
It's also worth noting that the UK is not the only country where bikes are permitted on trunk roads. They are also generally permitted in Spain, for example the US, Hungary, Spain (though Spain isn't in the above table).
table), and so on. A mass edit would be a sticking plaster to fix the issue in the UK while leaving the (much bigger) US unresolved.
Producing country-specific bike routing isn't difficult. [cycle.travel][2], for example, permits bikes on trunk roads in the UK but not in (say) Germany. One easy solution along these lines would be for the Garmin map producers to use Osmosis to change tags when preprocessing the UK extract - for example, changing `highway=trunk` to the `highway=trunk_uk` you suggest.
[1]: http://wiki.openstreetmap.org/wiki/OSM_tags_for_routing/Access-Restrictions
[2]: http://cycle.travel/map
