Not sure there's a need for the Gorn to be from another galaxy. I guess it depends when they're supposed to have arrived... If they only just did, that's harder to hammer back into continuity.
"Bound" established during Enterprise's 22nd Century, that their hegemony was known about by the Orion Syndicate - a member of whom poured Archer a drink they had created, warning the less he knew about them the better.