Still at home, and now this morning all of the routes that were broken as per my original post, and seemed to be fixed as per my second post, are now broken again... Also broken is Cockfosters to Wandsworth, which is now behaving the same way Cockfosters to Balham did originally - either not returning any route, or returning two routes one of which stops short of the destination.
Cockfosters to Fulham, Finchley, and other destinations closer to the origin, all seem to work OK. Cockfosters to Catford and Brighton also work OK, once again indicating that it's not a simple distance-related bug. The calculation for the Brighton route also took considerably longer than any of the failed route attempts, suggesting also that the routing engine isn't simply timing out whilst trying to generate some of those shorter routes.
Cricklewood to Wimbledon works fine, so it doesn't appear to be a basic problem with the map data itself - between the successful Cockfosters-Fulham and Cricklewood-Wimbledon routes, all of the required segments and junctions have been traversed by one or other of the routes, and with more than sufficient overlap in the middle to avoid any risk of it being a segment/junction somewhere in the Fulham area that might be causing the problem.
To avoid the A406/A10, I also looked at routing due south from Cockfosters. Routes to Kennington and Camberwell come up fine, yet routes to Herne Hill, Dulwich and Sydenham all fail.
I'm thinking algorithm problem at this point - breaking the routes down into smaller chunks allows routing, so it's not a case of incorrectly set segment directions/turn permissions etc somewhere between the overall start and finish points preventing routing at all. Distance, or at least complexity of the route, is somehow involved - as noted above it's not simply a case of "routes > x miles = failure", but perhaps more a case of "routes traversing more than x nodes or requiring more than y instructions to turn from one segment to another = failure". This could account for the longer distance routes (e.g. Cockfosters-Brighton) working OK, as they start to skip large sections of the urban crawl that's required for the shorter routes contained entirely within London, and instead get routed over the trunk roads which offer more miles per node/instruction.