How many units is enough? I don't know, and investigating towns is not cheap. An average of five cavalry per town should be sufficient to do the job, though maybe it takes them more than one turn. But the great skill of cavalry when ROP raping is being able to balance unit->town assignments after the start of the attack, due to their fearsome movement range.
In this map, I imagine 5 cavalries stationed at each red dot, ready to choose which town to attack, as indicated by the red lines.
In addition, we would have one cavalryman stationed adjacent to each town, because we know that each town will need at least one attack to take down.
Of course a plan like this is not so rigid that one should delay the attack unduly; if 90% of troops are in place and the other 10% will take another turn or two, then one may as well make the move right away and hope that the RNG is not set against us.
From all this analysis, I get one further thought; we need more units in Scandinavia than Germany. The Vikings have more towns, they may be re-arming with French saltpeter even as we speak, and veterans of that campaign will be needed to move on America, or support the American province against England, depending whether we do all three civs at once. The Franco-german border is short and easy to defend (defend the mountains well, forcing French units to head into the jungle), whereas the Anglo-american border is much longer, and we may be able to pick off northern English towns if they do not have much military spare in the area.