Magic is really just a lack of understanding as to how something works. A wizard or sorcerer is one who has the knowledge of how something works and is able to do it.

If People who lived in the 1300s were to visit New York or London today they would have no understanding of what makes anything work and would believe them to be magical cities run by powerful sorcerers. I'd imagine if we visited those same cities 1-2 thousand years from now we might think the same thing.

As scientists(present day sorcerers) keep working to uncover the magic of physics then we may, one day, be able to conjure fireballs seemingly out of thin air and launch them at genetically created monsters that have escaped from the local experiment laboratory.

To get to your initial question, for Magic such as telekenesis or elemental control etc., to never have been lost from ancient times would mean that people already had the knowledge to do this and passed it down through the generations or they were inherently/instinctually magical without the need to study how to make these things happen. This would mean they were magical because of some genetic mutation which would be similar to the X-men world.

In the roughly 4 thousand years of recorded history we has humans haven't evolved much. Since evolution of living things is based on mutations i'd imagine that magical people would be the same kind of magical for thousands of years. Thier technological advances would be the most measurable and noteable because the magical species variable.

I think the X-men universe would be the best example, that I can think of, for your scenario.