As someone who also enjoys an overrreaching story thread to an adventure, and one of epic proportions at that I would approach it this way.:
Begin campaign with a hook that will head the PCs towards the NPCs sphere of influence. This will be the main quest over several levels and once resolved the PCs will encounter the NPC at last.
Along the path allow the PCs to follow short side tracks that may be completely unrelated or not immeadiately related until much further along.
[sblock=You can even explain what your doing from the get go]
You can even explain to your players that the hook is the initial adventure, and all that you have been able to prepare, but at a certain point along the road it will reach a crossroad with many paths to follow where they will have to choose from there which direction to take. It depends on the experience of your players. Players new to RPG's will follow any hook almost without question, as it seems the obvious thing to do. More experienced players who have issues with feeling railroaded will know what the situation is and this may go some way to mitigating their discontent.[/sblock]
Here is an example of the rhythm from my campaign:
[sblock=Very simple start gives a Main Quest that heads them the right way] Starting Quest: Take this scroll to this place at this time. Don't ask questions. Here's some cash. More when delivered. Complication arises causing quest to extend to keep scroll and deliver it only to "El Renacuajo" on the other side of the continent. Warning: Be discrete in finding him [/sblock]
[sblock= The Journey across the continent with sidequests and character backstory hooks] I ran this as a series of encounters and skill challenges. Eg.
Skill Challenge: Escape town being hunted from the town guards
Encounter: Travel through a haunted grave yard in the mountains
Skill Challenge: Reach the Mountain Gate before the Snow Blizzard
Encounter: Get past the Agents disguised as farmers awaiting you at the Mountain Gate.
Change of Pace from fleeing: Urban Skill Challenge at next town to find a caravan to travel with discretely to reach the Merchant River before the Autumn Floods. A chance here for PCs to eplore town calmy, do some shopping and engage with a number of unimportant side quests. I had 5 possible caravans the PCs could join each a mini skill challenge: Hunter's Guild, Blacksmith, Spice Merchants, Town Guard etc.
The ways to travel can vary here with advantages/disadvantages. Eg. Not finiding a caravan would lead to a combat encounter along the way.
These variations let PCs feel like they are in control though they head in the direction you want them to go which is to "El Renacuajo".
[sblock=Use PC Backstories to inspire you]
Brushes with backstories are great to make you PCs characters feel like they belong to the world around them. So I had one of the character's backstories significantly change the pace of the story again once they landed at a main city on the other side of the Merchant river which was awesome. It wasn't something I planned to have become so significant but I was inspired by some very foolish play on my players part so I ran with the consequences. Initially it was meant to be some very direct questioning by corrupt port authorities who took a noticeable and direct interest in the group, particularly the Genasi Swordmage. His backstory was that of an escaped slave who had lead a revolution, fleeing from the gladiator arena where he had already won certain renoun. The arena's owner had dangerous agents out and about searching for him. The rest of the group all made up names and lied about where they were going to stay. The Genasi didn't get the whole thing at all and happily gave his real name and told them the name of the Inn they had been recommended by the Captain of their boat... hehehe ... so, it was all on!
Consequences: I changed the scenario from PCs become aware that Genasi is a wanted man to Genasi is arrested by hardcore Paladin Knights accused of murder. The agents had trumped up charges causing his arrest, using their corrupt contact within the ranks of the Paladins. Once they talked their way out of that they had to escape the agents shadowing them and each PC and find a discreet way of leaving the city with out being spotted by the vigilant agents. They took on work as brick labourers, hiding the genasi in one of the brick wagons that thye had to transport a few miles ut of town where a new Keep was being built at a very curious bridge.
The agents nevertheless would pursue them doggedly and they would have to now chose which path they would take to reach El Renacuajo. [/sblock] [/sblock]
[sblock=A fork in the road; both roads lead to Rome] Sohere the PCs have to choose a direction:
Continue down the main road to take a boat to their final destination: Fast road however the agents will have guessed their direction and they will have to overcome a very dangerous ambush
Or cut across wild country: Slow Road through Naga Territory: agents shaken but several dangerous encounters and possible side treks.
The choice PCs have here is real and significant, but they still end up where you want them to be at the end of the path: In the townwhere they are to find El Renacuajo [/sblock]
[sblock=Foreshadow large events; Mechanical hook into campaign]
If you want the PCs to engage with the larger story then foreshadowing what is going on with a mysterious event is a good way to do this. I used the Prophetic Dream device but had it coincide with a real world event that physically effected the PCs.
Prophetic Dream: Clue dropping, nothing overt, seemingly symbolic, wierd, mysterious but intertwined with major clues as to what is going on as PCs get more information in the future. Dream ends with the Evil from the dream directly seeing them with a scream "I see you" which casues PCs to wake up to a blinding flash in the sky and a part of their body burning.
Mechanical Benefit: They choose which part of their body is burning: Eyes, Hands, Feet etc. Depending on where they choose they receive the small mechanical benefit of having a Spellscar in that place. The power that caused this is the evil god which saw them in the dream, though they are not aware of this.
These scars will be used as story hooks later on. [/sblock]
[sblock=Making the most of sidetreks]
Not all sidetreks have to be inconsequential. They can add a depth, complexity and richness to your main story line. In my adventures I like to have loads of diverging, intertwiining and conflicting story lines. There is a story there but PCs choose which side of the coin that want to be on. I don't like to have bad vs good. I prefer bad vs bad, good vs good, bad and good vs good and bad, and every tone of grey mixed in between the starker contrasts of morality.
[sblock=How a side trek became a major plot example]
Travelling through Naga territory PCs travel across a cursed desert. At the oasis a group of nomads offer hospitality. They are snake men in disguise hoping to drug PCs and take them to the temple beneath the sands to be used in a sacrifice ritual to open a sealed part of the temple.
PCs saw through this and defeated snakemen. They could have carried on their way. They CHOSE to go inand explore the temple.
Temple story: The temple was dedicated to the Feathered Snake, daughter of the god of Poison, Zehir. However her brother took refuge here to hide from his father's fury after a failed attempt to assassinate his father and take his place. In his fury Zehir cursed the jungle and turned the place to desert, burying the temple and surrounding it with a huge snake guardian. Zehir's son works to break his sister's seal that keeps him from the inner sanctum which houses a divine crystal, an artifact capable of miraculous things such as the rebirth of a god. His sister has sacrificed her own life to seal this forever and prevent her brother remaining in a physical form.
The PCs engage in trying to cleanse the temple of the evil presence destroying Zehir's rebellious son. However Zehir himself manages to manipulate the PCs into helping him open the inner sanctum and use a part of the divine crystal to incarnate him with the promise of power.
PCs receive boon: Special Magic item and bonus Feat: Expertise on the condition each one perform a task for him.
He also reveals a big part of the overreaching plot, saying that all the gods of good are blind to what is happening but those that live in the darkness know what moves in the darkness. He says what is happening is far more terrible than him and even he must stop it or cease to exist. The evil he speaks of is the main evil that is behind everything and that caused the scarring. All Zehir says is true, but being the evil god he is he will fight against the bigger evil but all for his own terrible and selfish ends and in a way that will see him rise in influence and power.
Result: PCs have another major quest hook from a previously unthought of angle which hooks them further into the main adventure. Things are clearer for them. They are morepowerful. But they will pay the terrible price of seeing the consequences of making such a dark deal as the adventure progress. DM gains hooks galore into future adventures!!! A new major player and his minions comes to the table. They just incarnated Zehir, God of Poison for goodness sake and they each owe him a task! Muahahahaha (evil DM laugh ... enjoy your new power while you can! [/sblock] [/sblock]
[sblock=PCs finally reach their destination]
So once the PCs finally reach the place they are to find El Renacuajo I have had time to design a big major base city that will be where adventures spring from for the rest of the heroic tier and will be where the final battle scene takes place to have them moveto paragon path. I can say all that in retrospect but at the time all I knew was that here the PCs would reach their first major junction in the road, after which I nothing but loose ideas sketched out.
I didn't want to develop anything that I would never use because the PCs chose to do something else instead.
Upon arrival I had a number of events go on in quick succession that resulted in 5 or 6 different major paths the PCs could choose to take. Eventually most of them would lead towards the ever elusive EL Renacuajo but they are quite seperate adventures, yet remain facets of the same many sided gem.
Here I explicitly said to my players. "Alright guys congrats, you've made it to the first major intersection of the adventure. Here are the 5 different directions you can take. If you want to ignore them all and do something else that is fine too as i have nothing beyond here prepared. Once you choose a path I'll develop that path adn we can continue playing. Thankfully they were into the adventure by this stage and chose to pursue it. But they chose how they wanted to pursue it. [/sblock]
And so the rhythm begins anew. Narrow reaches a branching point. Choose a branch, and so the path narrows again until the PCs reach a new branching point. Add side treks, meaningful or not, variations of paths, alternate ways of dealing with situations, add brushes with PC backstories to taste and let the story breathe and have life, changing as your PCs actions impact it. Let them inspire you
