I've searched on the internet for any information about this error message returned by the MapPoint web service but haven't been able to find anything, so this is a rundown on what I've found, although this is fairly obvious stuff.
Say you're trying to route between points A, B, C, D and E. Basically the error is saying that MapPoint was unable to route between at least two of these points. So the first thing to do is figure out which points MapPoint didn't like. this can be achieved by breaking the route down into its constituent parts and try to route A to B, B to C, C to D and D to E. The chances are that at least one of these will fail.
Now it's time to take a closer look at the two points that failed. I think the best way to do this is to visualise the route using Google Maps and/or Live Maps. For me, both sites successfully routed between the two points but Google Maps showed something strange. The suggested route involved driving to a T junction, turning right, driving to the end of the road and making a U turn and driving back along it. Moving the point to the end of the road with the T junction fixed the MapPoint error. For me, being able to route between the points was more important than being completely accurate. I'm not sure what the solution would be if complete accuracy was required.
There's now a Live Maps web service that seems to have a very similar API to the MapPooint web service. I've not looked at this too closely but I'd be interested to know if it has a better algorithm for routing so these kind of errors are reduced. I'd also be interested to know if people have found different solutions to this error message.