Nash's original proof of his famous isometric embedding theorem was extremely complicated. I'm under the impression that very few people ever read or understood the details. The hard step is a generalized implicit function theorem. His proof was simplified considerably by Moser and others (I learned the proof from a paper by Sergeraert). However, the proof of the isometric embedding theorem was dramatically simplified by Matthias Gunther, who found a way to use the standard contraction mapping argument and eliminate completely the need for the so-called Nash-Moser implicit function theorem.
However, Gunther's proof, unlike the other examples and the intent of the question, is for me just as mysterious and miraculous as Nash's original proof.