Rumor Bosses spawn in the background, about 3%(?) chance per boss type (there's lots of them) per hour of game play, making about TWO appear per hour of playing (often more). Once a Rumor Boss appears you have a chance to hear rumors about it by gossiping at inns. You also can stumble across it without knowing about it (gets awkward if it's a Lich!). If no Rumor Boss spawned, than no amount of gossiping will hear about it.
Worth Restating: Rumor Boss Spawning Is Indifferent To Gossiping! Gossiping will help hear about a boss that spawned but won't make one spawn. You can waste 50,000 gold and it will do no good if the boss didn't spawn.
Best advice: Run Town Hall Quests or spam a dungeon for XP and rare drops. While doing that, the periodic inn check will let you know if a boss spawned.
Note, if you're running a lot of Town Hall Quests, rumors at the inn can get crowded so pick a number of totat quests to run at a time that works for your level, and gossip chance least you risk having Town Hall Quests time out without any hints.
Also, just because a Rumor Boss spawns, doesn't mean you have to fight it. Some are best avoided at low levels.