It is a little fuzzy what, if any, diplomatic channels were opened between the Federation and the Dominion prior to the outbreak of the war. If the Dominion never established exactly what was their territory (rather than perhaps generally claiming the entire quadrant), then the Federation may have felt justified continuing to explore.
The few times that we did see anyone from the Federation trying to find someone from the Dominion to negotiate with it usually ended in a skirmish at best, or the death of many people at worst.
Referencing the same episode you quote in the question, the first official contact between the Federation and the Dominion resulted in the unprovoked loss of a Galaxy-class starship with all hands. Follow that up with "The Search" Part 1 and Part 2 when the Dominion captured the crew of the Defiant and conducted a interactive physiological experiment on the command crew.
Per the female Founder at the end of Part 2, the Dominion is about control and order. They judge solid-form races as threats, regardless of anything else, and to protect themselves they will go to any length to try to control them.
FEMALE: Ironic, isn't it? The hunted now control the destinies of hundreds of other races.
ODO: But why control anyone?
FEMALE: Because what you control can't hurt you. So, many years ago we set ourselves the task of imposing order on a chaotic universe.
KIRA: Is that what you call it? Imposing order? I call it murder.
FEMALE: What you call it is no concern of ours.
ODO: How do you justify the deaths of so many people?
FEMALE: The Solids have always been a threat to us. That's the only the justification we need.
ODO: But these Solids have never harmed you. They travel the galaxy in order to expand their knowledge, just as you once did.
FEMALE: The Solids are nothing like us.
So while the Federation may have been guilty of violating Dominion space (this is unclear), the Dominion itself hardly gave the Federation any opportunity to apologize for that or broker any sort of right-of-way.