Luck has a lot to do with everything!
And in this game, they give you the option of just throwing him in there and hoping he doesn't get caught, or of taking your time and carefully crafting the cover and tools and whatever else he needs to successfully perform his mission. I gotta give em credit for that, at least. What I don't like is spending several turns' worth of income on a single mission and then always have it fail.
I have yet to see an enemy AI implant a spy on me, and I occasionally make the check, not that the AI needs a spy. They already know where all my units are. I usually also go for Democracy, so Propaganda is out. They already know what I'm building. Not much else for them to do.