The CEC in ToA has a 20% Approval bonus. Use it to replace existing approval buildings you may have - it does double duty, so it is not wasting a tile. I always build them - I hate to waste spies on counter espionage when the building is releatively cheap and has another use too. Training a spy is just too darn expensive to waste it on nullifing another spy.
I use spies pre-invasion to bring down the morale. Will hit every morale structure on a planet - use the Propaganda Invasion; after winning you g et them back immediately. You can conquer several planets in a turn using the same 10 spies. I usually will only train about 20-30 per game total. Try to keep at least 10 on hand to make themm really effective.
I recall reading somewhere a long time ago that the total population size of the target aI is a factor in how long it takes to reach a certain level - i.e. low, medium, high, advanced. Therefore if you plan on using spies, do it early in the game and you will get to at least medium on all opponents rather quickly. Once their pops start expoding, it takes more spies and more time to reach a new level. (This is speculation on my part - perhaps someone can prove/disporve it - but it seems to play out that way in my games.)
I rarely go beyond High - usually am content with medium. Advanced can take forever to reach, and it really only gives you a miniscule chance of stealing a tech now and then. Too much risk of losing an expensive spy for little overall gain - they are exposed way too long.
You can get a feel for when the target opponent is ready to start nullifying your spies, or even a good guess that they have multiple spies available by checking the Stats Tab in the Foriegn Relations screen over a regular period of turns. You can see how much they have allocated to espionage spending there - and can extrapolate when they will have a counter spy ready. If you do not see a line for Espionage spending, they are not training any spies, so you know it is probaly safe to leave your spies on planet for a long time with little risk. Eventually the aI will start to spend mega amounts on espionage - you then know it is time to pull youir spies and come back later when they are not spending so much. Send them on to the next target.