To answer this question, one must first define science. Luckily enough, a definition exists and is very specific.
To make advance via science, one must do the following (I admit I'm just copying over from Wikipedia):
- observe universe;
- come up with a question;
- postulate a falsifiable hypothesis (i.e. such that it can be rejected in an experiment);
- make predictions based on that hypothesis;
- test predictions in a reproducible experiment.
A hypothesis is considered good (and renamed to theory) as long as its predictions hold. Then it's either thrown in the trash can (phlogiston), amended (which species evolved into which), or narrowed to a scope where it still holds (Newton's mechanics < Einstein's relativity). The whole point of falsifiability is to only keep theories that work.
And it seems that such approach yields some great results indeed, at least in our universe, and they can be replicated on large scale as a bonus.
Now the requirements for magic to coexist with science are:
- it's part of how universe works (otherwise you can just wave hands and not ask this question);
- it's obviously efficient (or science overcomes);
- the universe can still be studied scientifically in general (or no science at all - at least science as we know it);
- one of the rules above has to be broken in case of magic (otherwise converges with science).
Of course, one can think of a magical knowledge process completely different from a scientific one, but I wouldn't even try to take on such broad topic.
Now breaking (1) and (2) is obviously out of question for a sentient being. (4) seems too practical to be avoided, as in "I'm casting a spell, but I'm unsure if that's fireball, invisibility, or healing".
(3) seems more like a divine power to me. As in, God exists and His existence cannot be disproved, and all experimental outcomes are altered at His discretion.
So we're left with breaking symmetry (5) by exclusion: magical experiments that, unlike scientific ones, cannot be fully reproduced based on a reasonable description.
However, if magic is completely unreproducible, it will be too unhelpful. First off, it should be reliable enough for the mage him/herself. If it is completely irreproducible by others and has to be learned from scratch, it will get surpassed by science at some point (shotgun invented = fireball useful no more).
Now my suggestion is as follows (YMMV):
- Magic depends on the mage's personality and is mediated by their own body perturbing a chaotic physical process of choice (the setup is impractical to reproduce until very advanced science).
- Envisioning the desired result is required for a spell to work (or else butterflies flapping their wings will ruin the whole world).
- Magic can be taught, but individual formulation of hypotheses is still required from every pupil.
- Last but not least, mages can take state of the art scientific theories into account. E.g. cure disease spell < kill a virus spell.
In such setup, magic is going to be one step ahead of science for individual usage and two steps behind in mass usage, creating a shaky equilibrium. Well, at some point science becomes advanced enough to take on replicating a mage's personality, and the two finally converge, but that's a long long way to go.