He hasn’t gotten around the lead insulation problem. Granted he’ll be suspicious of anything coated with lead, that’s where your creativity goes to work. He’ll come to you in a number of ways, mostly requiring a kidnapping of someone he knows. But you can draw him out in a benign way. And when he’s weakened, do him in immediately, instead of putting him in an un-necessarily-slow-moving-death-trap that even a mere mortal can undo buy just wiggling his toes.
Really? I thought it was just because Supes wouldn’t let him rob banks…
Luthor built a magic accumulator in the '70s; he thought it would generate a blast that could kill Superman, but it instead proved capable of zapping someone into a parallel universe. (It later proved capable of siphoning off some of Captain Marvel’s enchanted thunderbolt, which Lex then used to turn Cap back into Billy Batson.)
And in the '80s – specifically, in MIRACLE MONDAY – Luthor is sitting in his prison cell and starts wondering whether thoughts are matter or energy; he eventually concludes that, even as E=mc² implies the ability to convert matter into energy, so too can matter and energy be temporarily converted into an equivalent amount of pure thought. Luthor also promptly deduces a number of interesting things about the afterlife; upon switching to an organic diet and taking up meditation, he dematerializes behind bars and rematerializes in New England after journeying through hell.
(And in the '90s, when his cloned body started breaking down, Luthor sold his soul to Neron for perfect health – before acquiring the Philosopher’s Stone, which he used for everything from classic mind control to encasing Plastic Man in a bottle.)
Scientists in our world don’t respect magic because it has never been proven to exist, I’d expect even a scientist in the DC universe to actually be intrigued by functioning, provable, reproducible, controllable magic.
Luthor’s main motivation is he wants to prove he’s superior to Superman. So he wants to beat Superman with his own abilities. Beating Superman by the use of some outside help like magic or alien technology or a powerful ally wouldn’t satisfy him.
I’ve always felt that the real reason Luthor hates Superman is because he subconsciously recognizes Superman is better than him. If Luthor had Superman’s powers he’d use them to make himself ruler of the world. But Superman has willingly chosen to not abuse his powers - a choice Luthor subconsciously knows he couldn’t have made. If Superman acted like Ultraman, Luthor would still try to defeat him. But if that was the case, it would only be because Luthor saw him as a rival and an obstacle - there wouldn’t be the obsessive hate.
No (in most interpretations) Luthor is quite consciously aware he couldn’t have made that choice. He also doesn’t really believe Superman did. Or anyone else would.
For the most part, the story is also quite clear on the fact that Luthor’s claims that Superman, as an alien, diminishes humanity, and thus he has to prove that Humans are better, are nonsense, and that Luthor’s real motivation is that he can’t stand for someone to be better than him. (They vary a bit on whether Luthor, himself, is aware of this fact, and is just lying, or if he’s successfully deluded himself.)
In '05, Rick Veitch did a trippy QUESTION series where Lex (a) plans to kill Superman with chi via feng-shui architecture but (b) is foiled by an urban shaman.
You know, all this brings up an even better question: Why doesn’t Supes learn magic? You can’t say that he doesn’t need to, as his vulnerability is a clear liability in some scenarios. Maybe he’s just too busy? Given that he has a huge fortress to store stuff in, it’s surprising he doesn’t collect all kinds of artifacts to bolster his arsenal.
That’s it. It’s the Batman reason.
In one late Silver Age comic Dr. Fate offers to give him a shield that will protect him against all magical attacks. Superman declined because he felt that if that happened he would have no real weakspots (kryptonite having been removed as a threat at the time), and wouldn’t be able to identify with the average human.
In other words, Superman is already so powerful as to make it hard for him to be believably threatened: taking away the little that is left or making him even tougher just paints the writer in the corner.
Deep down, of course, the real reason Luthor hates Superman is because he blames Superboy for his hair loss. 
Apparently in Luthor’s first appearances he had red hair. Due to an artist’s mistake, he showed up bald. THEN they wrote the oft-repeated story about Luthor’s hair loss as a reason. They also wrote monkeys into the stories whenever possible.
Everything’s better with monkeys.
So you make bullets out of kryptonite with a thin lead coating. Which will look, to X-ray vision, just like perfectly ordinary bullets made entirely out of lead. Which Superman routinely ignores.
All right, it’s been done. The bullets aren’t tough enough to penetrate, but the lead breaks off and, lo, small lumps of Green K begin to affect him. Heat vision, now, vaporizes it into gas which disperses in the atmosphere, becoming effectively harmless. Pretty much standard procedure. Unless he’s getting hit with a lot of bullets all at once there won’t be enough radiation to significantly hurt him instantaneously (that requires one of those hand-sized meteors Luthor loved to carry around).
But let’s say he’s had a few rounds with the Parasite already and the bullets do affect him. Supes is not a loner. JLA signal brings Flash to sweep the place, or some other of his hundreds of superfriends, and the villain is back off to jail just before the ad for X-Ray glasses.
To expand upon this a little - they think the artist either mistook one of Luthor’s minions for Luthor, or that they mixed him up with the Ultra-Humanite, another super-scientist villain (who was originally a bald man, has since been a woman, a giant ant, and an albino ape, the last of which became his most consistent form).
John Byrne, in his Superman/Batman Generations Elseworlds epic used both of those - Humanite transferred his mind into one of his minions, and went on to live as Lex Luthor. Luthor’s brain, meanwhile, became Metallo.
That was too awesome to not comment about.
OK, I know you are relatively new here and so am I, but let me welcome you to this little pocket dimension that some call the SDMB, Prof. Pepperwinkle.
Make youself at home.
Oh, I see.
You already have.
Good sport!
Why Doesn’t Lex Luthor Learn Magic?
Because then he’d be Doctor Doom.
Heh! Thankyouveddymuch!