A secret MLM (pyramid) company that offers eternal life, but in fact it transfers the life forces of its members to those position "above". If you get high enough, (meaning you get enough new members) you start to enjoy the benefits. Maybe a willing sacrifice is much more effective for the transfer. But no one says, that a suddenly unwilling member, threatening to tell the authorities, may not loose it involuntarily... thus start people to vanish, and aged corpses are deposited somewhere safe.
As the PCs travel the road, right after a bend they hear a sharp whistle and call: "Heeey, not so lazy, move your asses!" It is a large man that calls, and there are unwilling workers that listen. A small company, 10-15 men work on the road, push boulders aside, dig up roots from under the road, etc. The large man that shouted turns to you, smiles fast and mutters something under his breath, sounds like cursing some lazy worker. "Where does the road bring you from, travellers?" And does a little small-talk.
And what is really happening? A group of bandits is 'adapting' the road for shady purposes. The road will not be wider, but tighter, with enough cover around (and a few traps perhaps), and will become an ideal spot for ambushing travellers or entire caravans. The bandit leader wants them all to appear harmless. The 'lazy worker' he cursed was actually a guard that should give warning before any travellers come around (fallen asleep). Not surprisingly, the boss may decide for an ambush even now.
A rather large armed group slowly walks the road. Unless you get to see what they transport, you could think it is a caravan with expensive goods, or the soldiers escort someone important. But this is a prisoner transport, on the way to mines, criminals on their way for punishment.
The soldiers may be willing to talk, the captain will have a few questions on you and the road, but they will keep distance, and part soon.
You meet a large number of villagers, walking and weeping beside the coffin of an old bearded man (or adapt to your funeral customs). If asked properly, you learn about an old wizard, a wise man that long helped the tiny village to grow and prosper. Even after death he shows his favour: he gave most of his possesions to the poorer members of the community. All the villagers show him now respect this way. Why do you ask, are you adventurers? (As a last wish, he left a tiny case for the first group of adventurers that crosses the village).
Five men are herding fifteen horses down the road. They won't be very talkative, but are willing to sell a horse, or more horses if the heroes are interested. These men are horse thieves. They are already sought by regional militiamen. Anyone with a stolen horse (all are marked) may get into trouble. If found guilty, horse thieves face prison or even a hanging execution. Similar thefts have happened only a month before, and a reward is offered.
The Black Forest- actually a part of another forest, is said to be cursed by the presence of some horrific monster, which burns the very earth with its body!
No one has yet seen it and lived to tell, so be warned!(see NPC Aurelius Blackfoot for details)
Rather than making a baddy impossible to hit, consider giving it mega-hit points.
Super hard to hit leads to great player frustration. Allowing them to do damage leads to a sense of accomplishment. another variation of this would be to give the bad guy a forcefield that shows damage.You could also give them a mastermind ability that sluffs the damage of to minions who should be easy to kill.Once in a while a super high to hit encounter is ok ,but it should be few and far between.
Your mileage may vary