But it is almost impossible to get past medium espionage level with more than one AI.
I've found it fairly easy to get to advanced espionage level with multiple opponents. However, I do it in serial fashion. Drop all of your spies on one AI. Playing as the Krynn, that would be 15-30, depending on the stage of the game. When I dropped 30 spies on the Drengin, I got to advanced espionage level in about 5 weeks.
Playing as other races, it would take too long to make 30 spies, but dropping 10 or 12 on a race does cramp their style, and would take a long time for them to knock out.
I don't see much tech stealing happening though. From the description of 'advanced' you'd think that you would get their techs the turn after they did, but it seems more like a tech steal once every 6 or 8 months. Is the tech stealing rate tied to the number of spies you have deployed at the current instant?
I'm not sure about the cost-effectiveness of spying. It is certainly expensive, even if you have a big espionage skill. Of course, if you've been spending money on espionage for a long time, it's hard for any particular opponent to take out a significant number of them. If you reach the point where you can drop 30 spies on someone you are at war with, that's a pretty crushing advantage that's impossible to negate on any short time-frame. The most likely outcome is that almost all of your spies will survive to direct at the next victim.