Bede has an interesting post on witchcraft prohibitions in the Bible, comparing the Vulgate and King James versions of the same passage. (Seen via Claw of the Conciliator.)
In fact, I have read a very interesting history-of-ideas book on the history of witchcraft’s treatment in Europe by the Church. (I don’t recall the name and author, but it was somebody big.) The major point was that, for the most part, early Christians were not all that fearful of witches. Witches were just one more form of idolatrous worshipper, and the power and name of Christ was inevitably victorious over mere spells and prayers to demons. (In your face, Simon Magus!)
The whole thing with witches wasn’t of much concern until Christianity got wayyyyy out into the countryside. At that point, the urbane Christian missionaries found that one of their major charitable responsibilities was that of saving the butts of supposed witches and pagan priests from angry countryfolk who had bad weather, dead cows, sick kids, etc.
Christian decrees of that day said that it was quite possibly heretical to attribute any magical power whatsoever to witches, sorcerors, pagan priests, et al. Priests were encouraged to scold their congregations for holding such heathenish beliefs. The only power demons held over Christians was the power of illusions and lies. So it was strictly forbidden to punish or kill any pagan or witch for magical crimes; doing magic was foolishness which couldn’t actually have any effect. Only normal poisonings and killings proved by evidence could be punished.
It is only much later that you find Christians beginning to consider again that magic might work, that the demons might have more material powers, and that witches might be killed for practicing witchcraft. It again seems to have been set off by civil unrest, bad weather, outbreaks of disease, and crop failures more than any change in religious belief — though the turmoil of the Reformation does seem to have triggered a lot of the witch scares.
Also, as regards the Hebrew word for witch — I believe it is a word associated strongly with poisoners, just as the Latin and Greek words for witch are. The idea, at least in Roman society, was that you went to a witch for a poisonous potion if you wanted to get rid of somebody. (Some of the noble Roman ladies allegedly did this a lot.) IIRC, “veneficium”, poisonmaking, was synonymous with “maleficium”, evil magic.