Don't forget that reputations can be exaggerated as well.
Once had a group of PCs take care of a small band of Orcs (about 5 or 6) that were plaguing a small village. They bragged about it in the village tavern afterwards. There just happened to be a trader in there as well. At some point, they were asked where they were heading and they named a good sized town about 100 miles south.
The PCs went out into the wilderness and didn't get to that town until a couple of adventures later (they also went up a level or two).
When they got to that town, they heard all these rumors about how this powerful group was supposedly heading for this town. There were some who were afraid that they were bad guys, some who thought that they were heroes, some (of various levels, include some who were definitely much higher level than the PCs) who wanted to challenge them to make a name for themselves, etc...
After about 2 days, and hearing all of these rumors, it finally clicked that all of these rumors were about them. Since they had already seen two powerful individuals (more powerful than the PCs) come to blows about who was going to get to challenge the "adventurers", they quickly slunk out of town and from that point on were much much more careful in telling their exploits...
What had happened was the trader told the tale at the next village, and got a good reception from it (discount on room and food, better sales, etc..), so as he traveled south, he kept on telling the tale, embroidering it more and more as he went. And as he traveled, other picked up the tale and embroidered it even more...
By the time that the PCs heard the rumor, the 5 or 6 orcs that they defeated had turned into a murderous horde of several dozen, with eyewitnesses!!