(I'd prefer to make this a comment, but it's too long.)
I haven't seen "Crossover" and don't remember "Mirror, Mirror" very well, but there is a way to make this work-- at least well enough for a soft science fiction setting like "Star Trek".
Suppose there are many universes, and a mechanism that allows people to jump from one to another on rare occasions. And suppose that this mechanism tends to choose two universes that are nearby, where the cosmic definition of nearby is that some things in the physical vicinity (e.g. people, ships) are physically almost identical, but large and distant things (e.g. societies, races) can be wildly different. The bias also doesn't seem to apply to very small-scale things like brain patterns, so that although a "double" has the same face as person we know, he may not have the same personality. He might have a different name, too, but the Universal Translator can smooth that over. This is enough to explain either episode*.
To explain both episodes -- and the stated fact that both groups of people visited the same other universe -- requires something more. Just to recapitulate, "they went to the same place" means that when the DS9 officers found themselves in a strange version of DS9 (the station, not the series), they could consult the history books and read about something that happened a century earlier on board the Enterprise: some of the senior crew had acted goofy for several hours, showing mercy to enemies, unfamiliarity with shipboard disciplinary procedures, and surprise at the state of Spock's facial hair. Then they started acting normal again and reported having been on a version of the Enterprise weirdly bereft of torture and treachery, with a clean-shaven Spock and very few daggers. This corresponds exactly with the DS9 officers' memories of their own history, in which several members of the senior crew of the Enterprise had turned into disoriented, vicious, scheming psychopaths for a few hours, then recovered and told of-- you get the idea.
According to the "Nearby" rule, the DS9 jumpers should have found themselves in a self-consistent universe, in a station similar to their own, full of people who look like the ones they left behind, but with distant things different from what they remembered. It makes no sense that in such a universe, a distant group of people, a century earlier, should resemble a corresponding group from the travelers' home universe's history. It's not required by the "Nearby" rule, it can't apply to all groups of distant people (otherwise even one "didn't have a child" divergence would break the whole thing), and if it's not required then it's wildly improbable.
So let's add one more feature to the mechanism: laziness. It chooses two universes, A and B, that are similar to each other in a couple of different spots-- and those spots are where people can jump. It is pure coincidence that a universe that produced a twin of "our" Enterprise also produced a twin of "our" DS9, with no causal connection between them and everything in other places and times wildly divergent (although there may be other "twins" we don't know about). But that's just the kind of coincidence the Mechanism finds. This is an "in-universe" explanation that explains everything, but requires no explanation within either of the two universes.
(*) Don't ask me to explain how the uniforms can be so different, that just makes no sense at all.
