I would say that you want to have a sort of reverse-donut shape for the detail-level of your campaign: Lots of detail at the top levels, lots of detail about the areas surrounding the players, and not as much in between.
Think about how the information will be used by the players. Obviously the lowest-level stuff (inside-out) is vitally important... That's what the players are experiencing now. The high level stuff is important too: when a player thinks about the world they're in, they'll be looking for a high-level overview (outside-in).
The stuff in between (the districts in your example), just isn't very important most of the time. There will be a few that are (locations of natural wonders, or important characters). There will be a few that the players need to interact with. Everything else can wait until they're needed.
Leaving this middle-tier somewhat hazy has the added advantage of allowing you room to improvise. If you need a town, you can add it to the blank areas of the map. The same for a forest, or a river, or a lake, or anything else your campaign requires. Role playing campaigns are much more fluid than most other forms of fiction, and having the extra room to improvise can be extremely helpful.
Think about the real world
There are many conflicts in the real world, for many reasons. Look at news or a history book if you need inspiration. Not all of them are combat encounters, many might be detective work and exploration.
- Which church is allowed to tax/get the tenth in a village? Help the priests of Pelor against an attack by Asmodeus' children (insert $LOCAL_DEITY).
- Are there racial tensions between the races? Calm the mob of elves wanting to burn all halflings.
- Who illegally hunted a deer in the baron's forest? Free the arrested farmer or help prove his innocence so he won't be executed for his crime.
- A landslide destroyed the crop in the neighboring village, and they are running out of food. But giving them food from this village might lead to starvation in winter.
- A Party member is unfairly accused of theft. The punishment is cutting off the left hand. Fight the guards? Escape the guards (Skill challenge?) Prove innocence (How?)?
But much more important than the exact back story is in my eyes:
Make combat encounters diverse
It's not (only) the creature selection that makes an encounter interesting, but how you set up the battle. Let me make an example, with the same old 'bandit take village hostage' in three variations. I'm sure if you run it like that, the players won't complain it's always the same.
Devious, planning ba...ndits
The bandits have obviously heard of the wandering band of do-gooders and are prepared. First, they send in the dogs. Use skirmisher dogs that charge + make the enemy prone. Feel free to give them half HP or make some of them minions in order to make the battle shorter, but use enough different dogs they can't be locked down.
The dogs are backed by ranged attackers on the roofs behind chimneys - that means ranged attacks from cover, plus potentially combat advantage if they hid well. To get on the roofs, require at least a move action + athletics check. You can also make them minions, or at least some.
After two rounds, when the party is likely to be softened up, send in the Hog-Brothers, two large, burly fighters, brutes that will focus on the same target to make it go unconscious...
Trees are fun
Bandits have taken over the village, but the village is on a hill. When the party approaches, the bandits roll logs (trees) down the hills. That's a nice trap against Reflex that damages, secondary attack against Fortitude that slows. Once the party is up the hill, use charging brutes that push them down again. As always, use cleverly distributed archer minions to make it more dangerous.
Hostages
Again, bandits take over the village. Everyone is on the village square. When the party arrives, two bandits in the center threaten the peasants that were rounded up. Can the party lock down the two bandits and prevent an all-out slaughter, while fending off the other bandits? If you make the villagers run around frightened on the battlefield, you have another nice restriction: non-friendly area attacks kill peasants.
Build up a villain/villains
Don't worry too much about 'same backstory' for side encounters, it doesn't really matter as long as the fights are interesting. And you could build up a gang of bandits that terrorize the area... every session there's another gang-related side encounter. With time, the bandits also start hunting the party. This could tie diverse and interesting encounters together. Build one or two lieutenant for every side fight that has special capabilities (not magic, but either some leaderish/controllerish powers or a especially hard brute/soldier.
Best Answer
Most campaigns don't reach their end
That's just the way it is. Doubly so for your first ever campaign. You might lose interest. So might your players. You might realize you don't know what to do with them anymore. Life might intervene. Things happen.
And that's ok. Fun would still have been had. Memories would still be formed. The world you create might become a place for a next campaign - or inspire you to make a new one. As banal as it sounds, you'll learn from your mistakes (and discover exciting ways to make different ones). Don't sweat it.
Here, then, is some general advice on running a lengthy campaign.
Break it up into acts
Knowing as you do it's likely to prematurely end, plan for that. Have several major acts that would provide some satisfying conclusion. 4e's tiers work well here, though it does depend on the pace of your game - how quickly the PCs will level.
Perhaps in the first act, the war with orcs is a straightforward affair - they invade human lands and defeating their force is the end goal. In the second act, paragon-tier PCs venture into orc lands instead, to discover how orcs have changed. They also witness humankind begin its downfall, and make a decision in the end on which side to favor. In the third act, epic-tier PCs engage with the mystical source of knowledge and civilization (God? Artefact?) and rewrite the nature of man and orc. At that point, mortal kings are beneath their concern, as they deal with cosmic forces themselves.
Don't save the cool things for later
Do you have an awesome idea? Use it now! Don't store it until the slightly more appropriate time two years from now. By then you'll either forget it, it'll become irrelevant, or you won't get there at all. Make each session fun, not a prelude for fun down the road.
Plot it out
You have an idea for what you want the campaign to be like. Use some of the tools developed by others to help you get there. 5x5 method or Dungeon World's fronts, for instance. It won't do you any good holding it all in your head - get it out on (virtual) paper.
Change it up
Those methods tend to say this, but it's worth repeating: if the game goes elsewhere - that's fine, too. Never be afraid to change your plans. Don't stick to the one true path.
Play the same game
This is what kills most campaigns - people play different games at the same table. Use The Same Page Tool to set common expectations. And always, always, always talk to your players.