IMHO, the first of your requirements is pretty independent from the others and can be solved at a fluff level, without involving actual mechanics.
If magic is something that works by in-game consistent, measurable, explicable laws, it's more like another branch of technlogy. It works thanks to some physical law that's not working in the real world or is impossible for us to exploit or control, but in the game something made it possible.
Keep in mind it could still be magic, not technology, if the control exerted by wizards over this phenomena is not explicable with physics or made-up physics.
If magic works because it works it's still possible its effects get studied, but it's impossible to determine what causes them. They might be consistent, they might have fixed limits and boundaries but it's still impossible to know why it works.
Sometimes magic starts as described in the last paragraph and then becomes science when someone discovers some truth.
Have it clear that in your setting no such discoveries are possible.
The sheer fact that the characters act with this assuption deeply rooted in their mind should be enough to convey the "magic is a mystery" feeling you're looking for.
I'll make some examples:
In the manga air gear it might look like magic but it's technology and everything from people making solid clouds with teir rollerblades to that guy getting from Edmund Honda's shape to Goku's by burning energy in his body works because of some (wacky) physical explaination.
In D&D 3e's Forgotten Realms setting magic is some kind of technology. Wizards influence a sort of invisible network of magical strands called the Weave to form spells. They don't get spells where the weave is damaged. It obviously still looks like magic to those who don't know how it works. It still resembles magic if you think that you don't usually change the disposition of the weave when you're not willfully doing it.
Naruto's chakra system has an explaination of how pretty everything works, a physical explaination to magic again.
Star wars used to have none, until midichlorians were introduced.
Since this first point is pretty independant from the other two, I think we can focus on the others.
Any system that has rules for magic will give you some form of consistency.
Systems where very magic user uses the same spellcasting method are better in this regard, while removing differtiation between classes (classless systems work better in this instance) or between cultures (if some people use magic by dancing under the moon and doing tribalistic rituals and someone else is a psionic or prays the gods for spells the consistency is going to be reduced).
A system like Trollbabe's where half the world uses filters and potions and charms (the humans) and the other half uses shamanism (the trolls) can still be consistent. The important thing is to have a limited number of common approaches to magic.
Again, not too much of an issue.
Yes, technology can be taught, but the mystical gestures needed to invoke the mysterious powers can too, even if you don't know how it actually works.
This does not mean you can get away with anything that comes into your mind. There obviously is something you need to do to get this equal opportunity.
First, don't punish the players for not investing in magic since the beginning. If a character wants to learn how to dabble in magic he might need a new level of a magic using class, get some special feat or things like that but don't have his experience weight twice or thrice on him like D&D 3e did (less spells, less powerful spell level, less powerful spells from that same level).
Everybody can learn magic and it's not bad to do so after several levels.
There's a specific way (or several, depending on how you managed consistency) to get your hand on spells.
Systems where everyone can cast spells are the better to me because you don't even have the problem. Everyone can use magic.
You can use magic by holding magic stones is another good example of how things could work. Unfortunately mine is getting more a list of ideas because really, anything can work except the things that do not (which are whataver spoils the ability for a character to get his hands on magic).