Oh cool, a story question! Unfortunately, it doesn't have a clear-cut answer.
(Terminology: SSSC = the PlayStation English version; SSS = the original Japanese Saturn/PSX/PC version; TSS = the SegaCD release; SSH = the PSP release)
Let's start with the Vane Library. In SSSC, it says:
SSSC Vane library, left side, second shelf from front, first two shelves wrote:
When our world was newborn, an evil
force called the Vile Tribe tried to
conquer it.
They were banished by the Goddess
to the faraway Frontier at the edge
of our world.
The Vile Tribe has not been seen
since, leading many to conclude that
they have died out…
The Vile Tribe was a band of foul
creatures which knew only of hate
and destruction.
Without the intervention of the
Goddess, they would have had their
wicked way with our world…
But that first line, about the world being newborn, is a bit of a mistranslation. Temzin translated the SSS text for me:
Temzin's translation of the same books in SSS wrote:
Long ago, the Vile Tribe attempted to take over the world and were banished to the Frontier by the Goddess Althena.
None can survive the Frontier...there can be no doubt that the Vile Tribe has entirely perished.
The Vile Tribe were those who were steeped in evil. The despised all things and attempted to destroy everything.
かつて 世界を手にしようとした
魔族は 女神アルテナさまによって
辺境へと追放された
辺境では だれも生きぬけない……
魔族は すべて ほろびたに
ちがいないのだ
魔族とは 悪にそまった者たち
彼らは すべてを憎み
すべてを破壊しようとした
In TSS, rather than a book in the library, there's a NPC in Vane who says something similar.
vane-13 blue-haired purple-robed wanderer wrote:
500 YEARS AGO, THE VILE
TRIBE FREELY ROAMED OUR
LAND,
WREAKING HAVOC ON IT'S
FAIR PEOPLE.
HOWEVER, GODDESS ALTHENA,
IN HER WISDOM,
GATHERED THE VILE TRIBE
AND BANISHED THEM TO THE
DESOLATION OF THE FRONTIER.
Kizyr translated that NPC's Japanese text as "500 years ago, the Vile Tribe, who tormented people, lived in this world. But, the Goddess Althena, for the sake of the people, banished the Vile Tribe to the Frontier and sealed them there."
While there's no direct link between the Magic Empire of 1000 years ago and the Vile Tribe's banishment 500 years ago, the Japanese TSS strategy guidebooks say that "Vile Tribe is somehow linked to the Magic Empire - their descendants or creations." (From Shiva Indis's post here 17 Nov 2005.)
Lunar Genesis / Dragon Song muddies things further, taking place around 1000 years before Lunar 1 and having the beginnings of the Vile Tribe voluntarily living in the Frontier.
Lunar Dragon Song (my transcription) wrote:
Titus: That is correct. Originally the Frontier existed to confine those evildoers for whom there was no other hope... Until, that is, Ignatius turned his attention to it.
Gabryel: ...What did he do?
Titus: Through a terrible abuse of Black Magic, he took the fiends of the Frontier and molded them into a Vile Tribe. Now, he stands at their head, a terrible and mighty army of evil. The entire world is standing on the brink of being ruled by Ignatius and his Vile Tribe.
---
Adina: The Frontier... Isn't that where those who hate and oppose the Goddess Althena live? Why would you want to go there?
There is mention of the Vile Tribe potentially attacking human and beastman cities, so they are not yet confined.
This is all that I had easily to hand. If I remember, I'll check some of the other TSS and SSSC text for references. SSH's Japanese text is the same as SSS's almost everywhere, so probably nothing different there, and this is likely also the case with Lunar Legend.