But that's the point of spying, it's supposed to be expensive. If spies weren't destroyed everytime, they would just end up becoming too powerful. At some point you could completely cripple an AI with all your "recycled" spies. Hell you could probably completely cripple all the AIs and walk away with the game if your spies never died. Just crank up the spending and blanket the universe in no time. It would be too much of an exploit.
Yes, it's expensive. At the moment, it's so expensive that it's a total waste of money. My idea would be no less expensive, but you'd get an actual effect out of the money you spend.
It's already set so that the more spies you have, the more it costs to get even more of them. It's just that right now, it's hardly noticable since getting more than a few spies at a time is utterly pointless, and getting any spies at all isn't much better. So, with that being the case, it doesn't seem like spies are very expensive because you never get enough to really see the difference.
That being the case, if spies stuck around, you could get some and actually use them without them being turned into a total waste of money after just 1 turn, but they would also start to get more and more expensive as you got more and more of them. If they're still too cheap despite the ever-increasing costs, they can always up the rate of cost increase to further keep it in check.