It might just be easier to make a new travel failure notice for the smaller army. "The roads are blocked by an incoming army" or something to that effect, not unlike when you run into a dead end and it adds four hours to your travel time. I think I've had something like that happen to one of my characters while he was marching with his own army, in fact.
I think this is what you see when an infiltrator uses the "Disrupt travel" option. It is not random, and armies can already do that - provided they have infiltrators, of course.
