Quote Originally Posted by Cambyses II
Remember that the border fort will almost always replace your spy/assassin as the main counterspy if it is present. With a border fort in your province, your spies and assassins won't really have any opportunity to catch rival agents, as the that building will be doing their job.
And that reminds me that I haven't used this strategy yet: no border forts to have good valour spies and assassins....

Would you put both a spy and an assassin in the province, though? Spies are good for loyalty (and prevent civil wars?), maybe assassins are better for counter spying?

To answer another part of the question: to gain valour, for a spy or an assassin, you have two things to consider

1/ If you have Viking Invasion: the buildings for spy and assassin do have upgrades, making your agents start with +1, +2 or +3 valour

2/ When they succeed in missions they gain valour: I don't know if this always happens or not: 'might depend of the valour of the target.