The premise of Star Trek Voyager is that they are hurling through space as quickly as possible, trying to make their way back to Alpha Quadrant. They obviously get off course on occasion, but I'm under the impression that they are trying to make good time, and are usually rushing as much as technologically possible in a bee line way. So I'm curious how so many races they bump into have already heard about them. The phrase "word of Voyager's exploits" is used more than once. For these merchants to be aware of them would entail them having heard a story about some run in Voyager had with some species, then somehow leapfrogging ahead of Voyager and being in a position to be casually carrying on their business when Voyager happens to show up. Is it implied that there are sophisticated communication systems that keep different races throughout the quadrant up to date on stuff that might be happening on the other side of the quadrant?
The Voyager was one of the most advanced/powerful ships (replicator, teleporter (around 55 minutes in), hologram tech, weapons, etc) in the Delta quadrant, and was making a name for itself since they wanted allies to help them with the journey. A group like that does not stay anonymous for long.
In addition to the Sikarians being interested in Voyager's "stories", the Kazon were in need of resources (and thus political/military power) and were willing to do anything to claim Voyager. The Kazon controlled a large part of where Voyager started, meaning that they had much influence in the communication channels. They gave Voyager a bad reputation (first quote; not sure if it's from Kazon propaganda; can't find one that is) along a lot of Voyager's path, which in turn got those who believed in the Kazon to spread Voyager's reputation even further (I don't remember too many specific episodes where Voyager is unwelcome). Other spacefaring civilizations no doubt have their own [FTL] communication networks, which further spread information about Voyager, along with its reputation with each particular group.
Also, since subspace communication is FTL, and travels at warp 9.9997, it is already traveling faster than Voyager's maximum warp speed of 9.975. Combined with the fact that Voyager is not always traveling at high warp, or even flat out stopped (orbiting a planet, marooned, landed, etc), information has lots of time to travel.
Or if you prefer, tl;dr, gossip travels really really fast. Google something along the lines of
In the course of the episode, Harry Kim is transported 40,000 lightyears away. That's over half of the distance back to the Alpha quadrant.
Additionally, the Sikarians are highly interested in stories. Voyager's journey home would make quite a story all on its own, so there's not a whole lot of doubt that they would hear of its exploits while hopping around the galaxy. And probably spreading those same stories further.
In seriousness, calccrypto touches on one significant factor: Subspace communications travel faster than Voyager's maximum warp speed (apparently warp 9.9997 (although that statement seems to be uncited, it is consistent that subspace comms are faster than starships), compared to Voyager's top speed of warp 9.975). So in that respect, the Doctor is completely correct -- gossip does travel faster than (a ship at) warp.
The other side of the coin is that, while Voyager does want to get home, they spend a lot of time not doing that. It's not just "getting off course on occasion", although that does of course happen, but it's also that Captain Janeway and her crew are still at heart explorers, and jump at almost any opportunity to meet new cultures, to explore strange new phenomenon, or just to lend a helping hand now and again. To say nothing of the time spent acquiring fresh resources, making repairs, fighting/running from hostile aliens, or giving the warp engines a bit of a breather (maximum warp can only be kept up for so long, and even standard cruising speed isn't indefinite).
Plus, it seems like almost every other episode they're going dozens to hundreds to even thousands of light-years in the wrong direction, just to check out something neat or to respond to a distress beacon. That alone would give their reputation and rumors about their exploits ample time to stay well ahead of them, as every 1 light-year that they back-track is 2 light-years behind where they otherwise would have been!