Hmmm...why do you say that the Mystics could not have evolved without the Frozen Flame? (this may be a bit disjointed, so bear with me)
YES, the Flame sped up humanity's evolution, but the Reptites were already very advanced, even before Lavos fell. Obviously, the Frozen Flame merely helps the evolution process. Higher intelligence, however, can be evolved on its own. Besides, Ayla says some pretty intelligent things, though she says them in cave-speak. Obviously the foundations for intelligence are there--they just haven't fully evolved ways of expressing it.
Also, the Nu already have intelligence in the Prehistoric era. The Frozen Flame had nothing to do with this. Isn't it possible that the Mystics evolved normally, perhaps in another area of the globe?
Of course, if you're counting 'Mystics' as including not only Imps, but Henches, Diablos, Naga-Ettes, and the rest of Magus' troops, as well...
Then I'd have to say that they're probably Zealian inventions, as it's highly unlikely that such a lot of different monsters evolved intelligence.
Though Magus, Ozzie, and Flea could have given their troops intelligence, I suppose. Plus, there's that random Kilwala on the Denadoro level who can speak...Hmm...The rat in the future (and the Yellow Scout, and Sir Krawlie) can also speak, and show definite signs of intelligence, but that may be due to genetic manipulation before the Day of Lavos.
Oh, off-topic, but why is there a Yellow Scout in the future? It seems completely random. Did a random group of Scouts escape the Ocean Palace?
Anyway, that's all for tonight. I have to relinquish the computer.