This is an enormous question since you are asking about magical practices throughout the twenty centuries of Christianity across the enormous amount of geography included under this umbrella. I will assume that you are really interested in Europe - and by that the focus is popularly meant to mean Western Europe - and that you are interested in medieval magic or what is popularly regarded as fitting within that domain.

Villages would have people who seem to have a talent with manipulating supernatural forces for good or ill, and people would frequently come to these practitioners for help with cures for illness, obtaining luck with love or career, finding lost objects, or - on the darker side - to hurt someone. In general, we're not talking about the counterpart to Tolkien's Gandalf, if that's what you're after; these were small-time operators who might have an understanding of herbs or who might be using means that had no tie to anything "scientifically identifiable today" - as you say.

A good source from the historian's bibliography that I highly recommend is Keith Thomas, "Religion and the Decline of Magic" (1971). It's a classic and it is worth a read. A few paragraphs from the draft Introduction to Folklore that I am currently preparing may of use (but if you have specific questions, please ask and I will do what I can):

European folklorists historically focused on several aspects of oral tradition, belief, and custom. American and recent European studies have occasionally wandered further afield, but the European bedrock provides a place to begin. Folklorists study the annual seasons and holidays; the rites of passage at birth, marriage, and death; popular means to cure illness and injury; witches and witchcraft; belief in supernatural beings; and oral narratives. Except for the subject of oral narrative (folktales, legends, ballads, and other genres), the rest of folklore can be grouped under the heading of belief and custom.

One of the best examples of a comprehensive look at belief and custom is the Handwörterbuch des Deutschen Aberglaubens (Encyclopedia of the German Popular Superstitions), which appeared in nine volumes between 1927 and 1942. This is an exceptional work because it offers published material that most folklore archives only possess in unpublished form. A similar publication includes a wide variety of material from the Finnish collection: Suomen kansan muinaisia taikoja (The Old Magic Practices of the Finnish People), which appeared in eight volumes between 1891 and 1934. The final three volumes provide an example of the degree of detail possible. There are roughly 20,000 elementary ideas and their variants concerning the magical practices associated with cattle.

For European peasants (if not for non-industrial people in general), the world was filled with the supernatural and its potential. They believed that a wide variety of supernatural beings came and went freely about the world. This could occur any time, but nighttime, special days, and specific locations could require extra precaution. People also believed that there were magical practices one could and should undertake to protect oneself and to manipulate the supernatural to eke out a better existence.

Two examples demonstrate that some traditions survive both industrialization and immigration. North Americans preserve the preventative practices of knocking on wood and throwing spilled salt over one’s left shoulder (although the latter is quickly dying). Both acts were to distract the supernatural from during harm. Traditionally, Europeans used magic in various minor ways on a daily basis. Expert practitioners developed the generally accepted techniques and beliefs into a refined craft, but they did not deviate from the core beliefs of their culture.

Much like the questions around heresy in the high- and late- middle ages, did 'heresy' exist in opposition to 'orthodoxy' or did orthodoxy require heresy to be created? More precisely, dd heresy only exist once Catholicism started looking for it?

In this same way, I refute the the basis of the question: 'These individuals did something which was later identified as magic. That something is scientifically identifiable today.'

In Summis desiderantes affectibus of Innocent VIII we can get an inkling as to papal views on what constituted witchery, sorcery and magic:

[many are] unmindful of their own salvation and straying from the Catholic Faith, have abandoned themselves to devils, incubi and succubi, and by their incantations, spells, conjurations, and other accursed charms and crafts, enormities and horrid offences, have slain infants yet in the mother's womb, as also the offspring of cattle, have blasted the produce of the earth, the grapes of the vine, the fruits of the trees, nay, men and women, beasts of burthen, herd-beasts, as well as animals of other kinds, vineyards, orchards, meadows, pasture-land, corn, wheat, and all other cereals; these wretches furthermore afflict and torment men and women, beasts of burthen, herd-beasts, as well as animals of other kinds, with terrible and piteous pains and sore diseases, both internal and external; they hinder men from performing the sexual act and women from conceiving, whence husbands cannot know their wives nor wives receive their husbands; over and above this, they blasphemously renounce that Faith which is theirs by the Sacrament of Baptism, and at the instigation of the Enemy of Mankind they do not shrink from committing and perpetrating the foulest abominations and filthiest excesses to the deadly peril of their own souls, whereby they outrage the Divine Majesty and are a cause of scandal and danger to very many (...) the abominations and enormities in question remain unpunished not without open danger to the souls of many and peril of eternal damnation.

Beyond generic 'incantations, spells, conjurations' and 'charms and crafts', all we are left with from a policy perspective is the effect of witches: dead babies, ruined crops, ruined animal herds, and various torments. None of this is some basis, and no inquisitor's manual elaborates any further the 'basis' of witchcraft.

No, the question must be reframed. And in as much as I respect /u/itsallfolklore 's detailing certain 'magical practices', we must not mistake the order of accusation of witchcraft and sorcery, and the evidence thereof. The accusation came first, usually for inter-neighbour conflict and/or political reasons, and then the evidence was filled in to support the accusation. Any evidence would do. Effectively this meant that two self-same women who used herbs to heal wounds might face completely different futures based on other issues completely unrelated to the nature of their activities: one might be tried as a witch and the other not. The herbs had nothing to do with founding the accusation; their proximity to other conflict would have everything to do with the accusation.

You might want to repost this question with a specific time period and geographical region in the title. As it is, the question breaks the 'no throughout history' rule of the sub.

Timothy Knab wrote an ethnographic work titled A War of Witches about the people in a small village in Mexico and the conflict that erupted between two large families shortly after the revolution ended. Many of these people were killed using traditional brujo methods which Knab eventually learns from the last two surviving people from this period. I highly recommend this book if you want to look into that area. It is fairly cheap on Amazon and is a short read.

I can give you a bit of an idea about the Renaissance era. This was covered a bit in my undergraduate studies. I specifically remember my prof saying that in Renaissance Italy, it was kind of expected that a gentleman would dabble a bit in magic. It was just what one did, as an educated man.

What the something actually consisted of sometimes involved a lot of the things you might expect from having played D&D: talismans, incantations, etc. But what they mostly did was read and write. In fact, magic per se is fairly difficult to distinguish from religion, science, medicine, and philosophy, which are in turn difficult to distinguish from each other prior to the Enlightenment. For example, a Renaissance practitioner of "magical" medicine might diagnose your medical condition as having an astrological origin. He might then prescribe a treatment involving talismans and Orphic music. The talisman would have been created by performing rituals to draw down the powers of the stars and entrap them in the talisman, which would then be given to the patient. If you were suffering, for example, from melancholy, he might give you a talisman imbued with the virtue of Jupiter (to encourage a more jovial temperament). Conversely, if you were someone a bit too proud or manic, he might give you a talisman with the power of Saturn (to make you a bit more saturnine).

The above is an example of the way in which, during the Renaissance, various preexisting strands of thought such as Hermeticism, Kabbalah, Platonism, Neoplatonism, alchemy, and astrology were wound together and synthesized into more-or-less magical thought-systems by Humanists, Scholastics, and "Renaissance men" such as Marsilio Ficino, Pico Della Mirandola, Giordano Bruno, and Heinrich Cornelius Agrippa von Nettesheim. You can find many of their writings here.

I'm not clear on the time frame that you're asking about, so here's what I know about one piece.

There was [and is] a magical system specific to the African-American Christian population in the American south. Practitioners were/are not really considered magic practitioners, but spiritual workers who petition YHWH and work his will upon the world. They specifically do YHWH's work--all practices are done under his guidance and approval and, without it, the work doesn't 'stick'.

Traditional practitioners also did't refer to themselves as witches/sorceres/magicians/etc. In fact, there were specific proscriptions to keep witches out or defeat a sorcerer. More often, they were called doctors or root doctors or two-headed doctors. They often took titles such as 'Dr. <Name>' or 'Aunt <Name> or 'Papa <Name>'. All of those titles conferred meaning as to what they did. A doctor prescribed for your spiritual malady and a two-headed doctor might prescribe for your spiritual malady AND prescribe herbs or other beneficial things for your health, as health was tied directly to spiritual condition.

As to events, anything was fair game for spiritual work at the hands of a practitioner under the watchful eye of YHWH. Need to keep your man at home? Here's what to do. Woman at your job trying to get you fired? Here's how to manage her? Want to buy the house down the street? This is what you do. Under spiritual attack by the forces of the devil? This thing will help.

The things they did were wide and varied. Spiritual baths were common, as was candle work and prayer using Psalms and other bible verses as magical spells. They anointed the body, used 'personal concerns' [items connected to a person via physical contact or body processes--most common was underwear, socks, hair, fingernail clippings, and sexual fluids], employed foot track magic [which is distinctly African], and did any number of other things to get stuff done

The practice mixes African traditional magic that made the Middle Passage, European folk magical practices, some First Nations lore, and a whole mess of stuff that is specific to the southern United States. First recorded occurrences are in the early to mid-1800s.