The possibility remains that magick was known to Allag, they seem to have an incredible knowledge of everything else. Compare how advanced the Binding Coil and crystal tower are compared to the rest of the world.
Notice also that the Garleans seem to mimic a lot of this technology for their own purpose - considering that Van Darnus was of Allagan descent it's not too far-fetched to think that he had an understanding of how these things worked.
But then, where did the Allag get their power from in such vast quantities so quickly?
Well, look at it this way; Nael van Darnus was granted his power from his Deity. Given that he is a descendant of Allag, it's entirely possible that they also worshiped the same entity.
Bahamut, the elder primal.
It's pretty reasonable to assume such, and that Bahamut could have given the Allag the technologies that defined their culture. It was only after their destruction and imprisonment of Bahamut that magic became lost.