For the original megadungeon that I started and gave a few test runs with the Yamanashi Group 2.5 years ago, I actually started with a list of rumors and built from there.
It was an interesting experience, because I was just bored at work one day, and started jotting down interesting sounding tidbits on a bit of scrap paper. I added to it over a couple of days, and had some ideas about some that I wanted to be true, a few I knew I wanted to be false. Most were left up in the air.
Then I drew maps, and started stocking.
When we played a few marathon sessions with the dungeon, I worked out rumors this way:
All the rumors were printed out, cut into individual strips, folded, and put in a box.
Every PC starts the game with 3+Cha bonus rumors, drawn randomly from the box.
Just going back to town allows PCs to make a Charisma check to get 1 rumor (more if they have a Cha bonus).
Any time the group goes specifically trolling for rumors, they get 1-3 from the box, depending on how they play it.
Interaction with non-hostile NPCs in the dungeon may net more rumors.
It worked fairly well. Some players shared their rumors quickly, others hoarded their knowledge. After a few PC deaths, they started sharing more openly. And they were using that information to inform their play in the setting.
With my Silverwood mini-dungeon sandbox at the Board Game Group, I tried the same thing. I think it didn't work for a couple of reasons. One, I never varied the rumors. Certain rumors kept coming up, and I should have taken those out between sessions. But I usually forgot to do so.
Secondly, I think too many of the rumors were warnings about powerful creatures, and not enough were about the locations of fabulous treasures or powerful magic items. Warning people that they shouldn't go to dangerous places is a good thing, but then where do they go? They needed more rumors that would actually lead them to adventure, not away from it.
Finally, I pretty much already knew which were true and which were false. So I didn't get forced into improvising interesting things on the fly in those games.
So what have I learned? If I ever get this new megadungeon off the block and take it for a spin, I'll need plenty of rumors (and decide later if they're true or not), I'll need to rotate new rumors in and old ones out every now and then (although I do like the idea of getting the same rumor more than once--it seems realistic for everyone to be talking about subject X, and makes the players pay a bit more attention to it), and I'll need to make sure that most rumors lead to proactive play, rather than hindering action.