My understanding is that it would overtax the processing resources to consider every possible route between the start point and the destination. Thus, waze only considers primary roads in the middle of long routes to make the processing time reasonable. What makes a road non-primary resulting in it being culled from consideration in the middle of a long route at this time seems to be the road type designation. At one time waze posted the following regarding routing penalties:
0-15 km - All road types are allows for routing.
15-20 km - All road types except Streets.
20-30 km - All road types except Streets and Primary streets.
30-200 km - Only Minor, Major, and Freeways.
more than 200 km - only Freeways.
This was never crystal clear and I think there have been changes, but there are certainly issues with waze not being able to route directly from point A to point B, when point A and point B are far apart and not directly connected by roads designated as a freeway on the waze map. A need to traverse primary streets or regular streets in the middle of long routes can cause problems. I agree that the routes you are looking for should be interstate/freeway almost the entire way, but sometimes its only a few non freeway segments that cause the problems. The symptoms of this problem are exactly what you are experiencing, you can route each leg of the trip with waze just fine, but waze won't route the entire trip. In an effort to solve this problem, Waze is working to adjust how they identify primary roads so that the road type is not the only consideration .