Все нижесказанное не есть мое имхо, а есть результат планомерных изысканий. Поэтому просьба бить не сильно :)
Изначально церковь с магией не боролась вовсе (маги приходили поклониться Христу, и ангелы их не отгоняли :) ). Церковь боролась с конкретными магами за их противодействие христианству. Пример: смотри Деяния Апостолов, эпизод с магом Елимой.
Впоследствии Церковь считала самой главной ересью не колдовство, а ВЕРУ в колдовство, распространенную в невежественном народе. На Руси колдуны и ведьмы подвергались церковному наказанию как обманщики и мошенники. Считалось, что магии нет вовсе, а если и есть, то не в силах что-либо сделать с крещеным верующим человеком.
Впоследствии в Европе по мере возрождения языческого мировоззрения (эта эпоха так и зовется эпохой Возрождения :) ) дьяволу стала приписываться огромная власть на земле, именно тогда его начали писать с большой буквы. И именно тогда началась в Европе охота на ведьм как пособниц дьявола. Кстати, в России охота на ведьм тоже была, но исключительно по инициативе народа. Образованное священство, в отличие от католиков, в магию не верило до конца 20 века.
Это, так сказать, историческая перспектива. А в настоящее время в России начался тот же процесс языческого возрождения, которым Европа уже переболела. Отсюда и новый виток охоты на ведьм.