Let me mention that the question is closely related to a more recent one http://mathoverflow.net/questions/48771/proofs-that-require-fundamentally-new-ways-of-thinking which I think also is about ingenuity in a sense. So indeed I was not sure where this answer better fits but I think the proof I would like to mention belongs here more.
This is Galvin's proof of the Dinitz conjecture: The Dinitz conjecture asserted that if you give me an n by n array and in each square you put a set of size n then you can chose one element from each set so that all the chosen elements in a row or in a column are distinct.
If all the sets are the same (say 1,2,...,n) then you just want a Latin square. You can simply chose at position (i,j) i+j modulo n,
Galvin's proof derive Dinitz conjecture from the Gale-Shapley marriage theorem (Actually he used a theorem of Maffray, related to the stable marriage theorem.). It is short, elementary and extremely surprising. ( I will try to find a link.)
