FWIW, I have seen similar problems with my Vista HCx (and Garmin RoadTrip on my mac!) failing to find a route where Cloudmade happily finds one. Perhaps the multi-tile routing problems mentioned at http://wiki.openstreetmap.org/wiki/Mkgmap/routing/issues#Errors_calculating_long_inter-tile_routes ? -- Ture