Get Towers, i always have like 2diplomats 2 assasins 2 spies in all my provinces hehe seems to help cathing them spies, they get valor by doing it aswell..;)