This gets tricky. You make an interesting point about alternate timelines, and it may explain the plot. The DS9 crew actually continued the show in a different timeline from that point on. That happened in another episode where their O'Brien dies but is replaced by another one from an alternate timeline, who is a few hours older.
The reason I'm arguing against that here is b/c of what the characters said in the show. They didn't say that they've now crossed into an alternate timeline where there's no colony. They said the colony never existed. That was the major ethical dilemma. Sisko eloquently summed it up by saying that as long as they exist in memories, they existed. All of that suggests that the real issue is that Odo wiped the colony from existence. Yet if he never existed, then how could he have prevented his own existence?
I'm not saying this is the only way to handle time travel, just that its how the writers handled it in this episode. Without resolving the contradiction. That's how I saw it. You may have seen it differently.