Silly me, I've been running one such complex campaign for a while now. There are 11 regular players, each has two, three or four characters (no, each player doesn't play each character at once).
The group is on an island where they and their NPC allies are the only real city (the nearest other city is over 3000 miles east, across a lot of water).
But, there are lots of baddies on this island (blue dragons, red dragons, the blue's allies, the red's allies, the blue's allies' allies, the red's allies' allies, etc., etc.). Included in the enemies are a small mind flayer city, a githyanki outpost, a beholder enclave, and tons and tons of giants and humanoids. (The really tough bad guys tend to be far removed on the island, and often in underground lairs, and often have one another as enemies--keeping the PCs a bit safer than otherwise.)
So, I have this mammoth 3-ring binder with about 300 NPCs and all their connections in it.
I work about 60 hours a week, I probably spend another 10+ just keeping all this campaign stuff in order.
Sigh.
But, the players are loving it--so it's worth it.
Dave