I like vonGenf's format.
HEre are things I think spies, if implemented as vonGenf proposes, should be able to do:
1. Attack specific, targeted nobles
2. Be bribed to go turncoat
3. Sabotage infrastructure, roads, etc
4. Steal gold
5. Burn food supplies
6. Scout the region they are in
7. Incite peasant unrest
8. Pass on messages sent to "everyone in region" or game updates like that
9. Reduce estate efficiency
10. Rob temples/guildhouses
11. Be given a general, "attack some random noble" order: can't choose a target, but higher chance of success maybe
12. If captured, reveal like a mini-torture report (maybe just 5-10 messages) of the character's messages (they wouldn't know everything that the character would know if tortured, but they might know something)
13. Investigate secret societies
14. Carry out investigations similar to ruler secret police actions
Obviously many of these would require gold, or have various risks of arrest, or even a risk of the spy going turncoat (I think it would be hilarious, for example, if the "rob a temple" option had a small random chance of the spy having a crisis of conscience and leaving your service to join the priesthood).
Furthermore, I think that, if a spy is caught and confesses who his boss is, that should still provide grounds for a ban for the spymaster. Though presumably this would greatly lower the frequency of infiltrator executions and such, which would then increase the number of infils I expect.