Upgrading your hideout helps reduce risk threat.
Choose larger cities over smaller ones. Spies will do better there.
Once your spy has arrived in a city, let him sit there until his risk threat is at 5%.
When spying a garrison, use the player search first to determine their military score. If it's zero...they have no army and it's not worth the risk. Spy their warehouse instead and see if it's worth the trip to pillage.
Also:
http://www.tacticalgamer.com/ikariam...ize-spies.html
:P