Is there anything canon about the years between TOS and DS9? Who knows what happened? Just because they coul be extra galactic conquerors doesn't negate the possibility of them coming into the galaxy, setting up shop and claiming territory. They could have been building up forces to strike and never did in anything canon, they could have gone against other species, I just don't see anything to this that makes my continuity alarm go off.