Keep in mind that cities get a lot of law bonuses in EB, making it trickier for spies to enter and half or more will likely die if they're fresh from recruitment. You might do well to keep your spies in one of your settlements with markets to make them trained and/or spy a little on characters outside of settlements before sending them in, increasing their chance.