Where do rumors come from?

I've finally been reading Jack Vance's Dying Earth novels. It seems a rite of passage into the inner mysteries of the dungeon-crawling hobby, after all. This will be relevant soon.

Rumors are an important part of adventuring in dungeons. It's through rumors that players often get their first pieces of concrete information about the dungeon. Without rumors, meaningful choices are difficult to make in that first foray. "Which entrance do we take?" boils down to a cast of lots without something behind it. "What are we looking for and where are we looking for it?" resolves no further than "For treasure," and "In the dungeon." In fact, it can move one step further back; often the way PCs even know there's a dungeon with treasure in it in the first place is through a rumor, though that's usually given away for free, at least at first.

We're all familiar with the old trick of the old man in the tavern/on the roadside/hanging by his toenails from an invisible petrified troll. The reason we're all familiar with it is because it is a time-tested method of rumor communication. However, unless we're in this for the silliness, we're also tired of it. Sure, you can sometimes get away with it if you steer very clear of the words "old man" and "tavern", but it's still pretty recognizable. So, how do we get rumors to our players without seeming hackneyed?

Often the answer is, "young woman in a tavern," or "grizzled man in a not-tavern" or some such. These are good answers, but let me put it to you that you can, at one stroke, tell the players about your local dungeon and flesh out your world before their eyes in an unobtrusive and wonderful way.

He saw a blue-white, green-white flicker against the foliage. It was a Twk-man, mounted on a dragon-fly, and light glinted from the dragon-fly's wings.
Liane called sharply, "Here, sir! Here, sir!"
The Twk-man perched his mount on a twig. "Well, Liane, what do you wish?"
"Watch now, and remember what you see." Liane pulled the ring over his head, dropped it to his feet, lifted it back. He looked up to the Twk-man, who was chewing a leaf. "And what did you see?"
"I saw Liane vanish from mortal sight—except for the red curled toes of his sandals. All else was as air."
"Ha!" cried Liane. "Think of it! Have you ever seen the like?"
The Twk-man asked carelessly, "Do you have salt? I would have salt."
Liane cut his exultations short, eyed the Twk-man closely.
"What news do you bring me?"
"Three erbs killed Florejin the Dream-builder, and burst all his bubbles. The air above the manse was colored for many minutes with the flitting fragments."
"A gram."
"Lord Kandive the Golden has built a barge of carven mo-wood ten lengths high, and it floats on the River Scaum for the Regatta, full of treasure."
"Two grams."
"A golden witch named Lith has come to live on Thamber Meadow. She is quiet and very beautiful."
"Three grams."
"Enough," said the Twk-man, and leaned forward to watch while Liane weighed out the salt in a tiny balance. He packed it in small panniers hanging on each side of the ribbed thorax, then twitched the insect into the air and flicked off through the forest vaults. - Jack Vance, The Dying Earth

 Sure, now that I see it in text, it seems obvious. Still, here are some possible similar answers:

1. Rivers talk. Larger rivers not quite that often; they've grown wearier of speech than their smaller cousins, but "babbling brook" isn't just a poetic description. With the right incentive (anything from helping clear the banks of that annoying snarl of trees from last season's flood to just being nearby), a river can tell you anything that has been going on in lands it flows through.
2. If you dance in the faerie rings in the forest, the Little People speak freely, though they might laugh at you for being so concerned with the doings of the mortal world, and you might end up with more (or less) than you bargained for.
3. When the moon is new and the stars are out, fireflies will arrange themselves in intelligible patterns, of maps or sometimes even short phrases. No one knows what intelligence guides them to do this.
4. The Akashic Record exists. Sometimes it impinges itself on a consciousness that hasn't gone looking to tap it. Maybe it's lonely? (This is, potentially, both a source of rumours and an adventure hook if you feel like doing a dream-dungeon.)
5. Owls are well-known for their wisdom, or at least their loquacity. In exchange for a small morsel of fresh meat, they will happily divulge what they know of the doings of the world, and they have eyes nigh everywhere.

The above are designed to be something that happens to the PCs. Once they know they can get rumors from unconventional sources, they might go seeking them out, but the beauty of the above passage is that Liane happens upon a Twk man. He knows it's a source of rumors. Your players won't, until you show them.