Something lives in the fog in a certain region and travels with the fog. Kidnaps or kills, or is simply heard and "felt". ... fog is rising, heed the warnings the elders spoke!
Small tavern in an out of the way town. Serve a wonderful delicacy that is simply outstanding. It is a creamy white consistancy, sweet, good to eat alone or a sweetener on any dessert. If the explore or ask they are shown where they get it. They breed a group of large catipillars or some other type of insect that basically spit the product onto a setup that they created for that particular reason. Or maybe the delicacy is the byproduct of feeding them something. Instead of city can be a traveller offering the food.
Mining in a certain area turns all exposed skin (maybe just parts that are actively disturbing the chemicals that cause the reaction) of the those doing the mining to a dark blue color. Will wear off taking as many years/days spent in the mine. ... meeting a party of blue-skinned humans armed with pick-axes etc. Strange disease? Demon offspring? Curse? If they meet only one ex-worker, they will very carefully listen to any stories he says, no matter if drunken or insane, or just makes up to get a beer.
Diseased people, (leprosy or any other such fear inducing disease) when traveling, will often times wear a cloak that entirely covers their body and ring a bell as they travel, used as a warning for any others to stay away. Could be used for a disguise or safe passage. ... you meet strangely cloaked people, sometimes ringing a bell. "Please give us something to eat, mighty heroes!" This is time to show how good they are.
Could come across a band of refugees. Could have been thrown out of their town by a tyrant taking of their land, bought out by somebody unexpectedly, fleeing a battle they know is coming their way. Could be proof of what they are searching for, hints and tips of what is to come, or just to broaden the reality of the world.
Young kid from last town has been following the PCs and doing a rather good job at it. PCs weren't expecting to be followed so weren't worried and the boy/girl was careful. Notice the follower a couple days out of town, kid ran out of food and started getting careless. Followed the 'mighty adventurers' to see if he could join them. Father is a wealthy merchant. Bring him home, bring him with, send him off? What do you do with an unwelcomed guest.
Rain slowly builds, thunder and lightning continue to roll in. Road muddies, horse/wagon getting stuck in the mud. Thunder strikes coinciding with a deep hole a horse just walked in, horse panics, breaks its leg (maybe just sprain?). Horse is decompacitated and the rain just went from pouring to an all out monsoon. Shelter needs to be found, horse needs to be taken care of, covered in mud, add the posibility of items being lost to the confusion with the wind and dealing with spooked animals.
There is a person who has a well-known reputation, probably involving something illegal. But this person is either very clever and crafty, or really like his or her privacy, for no one knows who this person actually is. As an added twist, perhaps this person is of an age that would noramlly be wildly inappropriate (say, a child is a much-feared bandit) or maybe not the expected gender or even race.