If you really want to get rid of spying (or at least put big bright lights above the spies' heads), why not remove the ability to directly contact foreign nobles from people who are not diplomats or Council members? Then the only way spying could happen is if someone changes class to diplomat, gets elected to a government position, is a member of a guild or religion, or actually enters a region that contains a member of the realm they are spying for (thus introducing that opportunity to catch them). (also leaves a great many ways to contact people from other realms, most of which are traceable)
And let's say you have some Evilists in your realm and you're at war with Evilstan; maybe the Evilstanis predict your army's movement one too many times and *bam*, suddenly all the Evilists in your realm are suspect.
