And, as a fairly long article in Business Week (I think) detailed a couple years ago, Android was actually the first choice over Windows Phone, but Google and Nokia couldn't come to terms: Nokia wanted to be able to use the official Android branding and use Nokia's existing services (mostly their maps), but Google's license doesn't allow that.
Having said all that, I can understand some of the conspiracy mindset around this. Nokia wrote Elop's contract in a way which basically gave him a huge golden parachute if the handset division was sold to someone else, and that really is nuts -- I doubt the intention was to explicitly reward failure, but it's damn easy to paint it that way. But this whole "secret mole" thing? Frankly, whatever one thinks about Microsoft's business practices, I don't think it's plausible that they're really clever enough to pull this off.