It depends what you mean by magic. Nowadays we communicate by bouncing invisible light off the sky, which would sure as hell qualify as "magic" to someone six hundred years ago.

The issue is that "magic", in the sense that I take Minchin to be using it, isn't a solution at all. No matter what the explanation is, once you've actually got it, it's not "magic" any more; it's "electrons" or "distortion of spacetime" or "computers" or whatever, the distinction being that we have equations for all of those things.

Take the witch trials, for example - to the best of my extremely limited knowledge, most witch trials involved very poorly-defined ideas about what a witch was capable of or what the signs of a witch were. If they had known how the accused were supposed to be screwing with reality, they wouldn't have called them "witches", but "scientists" or "politicians" or "guys with swords".

Admittedly all of those can have the same blank curiosity-stopping power as "magic" to some people, but "magic" almost always does. Which is why, once you've solved the mystery, it turns out to be Not Magic.