The crucial question would be the duration of a two-way trip between the Dominion and the UFP territory. Could such a trip have taken place within the timeframe of the existence of the UFP?
By the time of DS9, the UFP was a bit over two centuries old. Many of its member cultures were revealed in ENT to be older still, in terms of being interstellar players. USS Voyager, a starship roughly on part with the Dominion technologically *, was indicated to be capable of making a one-way trip in seven decades. Thus, even a fairly "conventional" reconnaissance mission would have given the Dominion authentic (even if not up-to-date) knowledge of the UFP.
I doubt this would have been a single 140-year recce run thither and yon, of course. But a stage-by-stage mission would certainly be a realistic assumption. Mankind apparently spread across Earth (in many of the documented waves) at surprisingly close to the walking pace of an individual human, dozens if not hundreds of kilometers per year; similarly, the Dominion might have extended its tentacles at significant speed as well, with outposts and other connections close to UFP territory within a century or two of the launching of a campaign in this direction. The ruthless empire wouldn't expand militarily as such - it would merely slither in through the cracks, as far out as it possibly could, the ruthlessness part coming in when the long-reaching tentacles were kept loyal to the central rule (with varying levels of success). For all we know, some of the familiar Alpha players were actually Dominion vassals or at least intelligence partners even before the wormhole was discovered...
Timo Saloniemi
*) Personally, I get the feeling that Dominion technology doesn't advance rapidly, and that the Dominion propulsive capabilities demonstrated in DS9 were already available a couple of thousand years earlier.