My own feeling was that Vic Fontaine's appearance in the Mirror Universe is supposed to mean that it's more than just another alternate universe. Instead, the two universes are linked inexorably and they mimic each other in certain ways.
It would also explain why the exact same people (genetically, at least) are showing up, and being given the same names, hundreds of years after the point-of-divergence (somewhere around Enterprise or between than and the Original Series).
As in, Vic Fontaine exists in the Mirror Universe because he's being a meaningful part of the Regular Universe.
That's just speculation, of course. Reading this thread has, however, given me the strong desire to go back and watch those episodes on their own as some sort of mini-series.