Well, I think there is a way to make espionage interesting without causing too much micro-management. You just have to change the focus of spies are used for.
In the real world, spies are used for three things: information gathering, stealing technology and sabotage.
Most of the proposals I've read on this thread have focused on information gathering, but in a game like Elemental, much relevant information will be given away to players without the need for spies, such as the location of cities, the number of units guarding cities, racial info, etc.
I therefore propose the following: a MOO2 style spy system. Here's how it works:
Your cities build spies. You can move them accross the map like regular units, but are invisible to enemies when on their own. They have poor combat skills.
Spies can enter enemy cities with little chance of getting caught. Having spies in a city gives you access to a bit more info than you can usually get. The more spies you have in the city, the more info you have access to. With 5 spies in a city (max), you'll know what buildings and units are being built, what's being researched, etc. Spies that are simply info-gathering have a very low chance-per-turn of being caught.
Spies in cities can also perform actions. These actions are more likely to succeed the more spies you have in a town. These actions can be accessed in the same way as other unit abilities. Here are the options:
1) Steal resources: Spies can steal common resources, such as money or building materials. Low chance of being caught, you can set spies to do this every turn without manually going back to the spy. When caught, a single spy is destroyed.
2) Steal research: Spies can leach research points each turn, and have a small chance of learning enemy spells. Spies have an average chance to be caught at this.
3) Sabotage structure: Spies can weaken or destroy defensive structures. High chance of being caught, and if caught all spies are destroyed.
4) Poison the Wells: Gives all defending units a bad status effect (eg "poisoned"). High chance of being caught, and if caught all spies are destroyed.
5) Assassinate unit: Spies can kill any unit stationed in the town. All spies are destroyed whether this action is successful or not.
These ideas give players two options: gather useful info and don't worry about your spies, or have them do stuff and possibly lose the info. There could also be the option of leaving spies defensively in your own cities to increase the chance of catching enemy spies. The drawbacks to spies would be the cost and upkeep of maintaining them. If spies are useful by just sitting around, they wouldn't force frequent game-play decisions on the player which might cause the game to bog down.
Do you guys like my ideas here?