I think you're substantially understating the difficult in recruiting spies. Any mistakes there and the recruiting nation would not only end up with double agents but also expose their handles, methods of contact, etc. Perhaps the biggest issue is that you'd need, as a foreign nation, to know more about the loyalties of intelligence agents than the country they're working for.

And similarly, I think you're greatly exaggerating the difficulties in obtaining US citizenship. It's a process that can take as few as 4 years. And thanks to our laws, people can simply have children in the US and they are automatic citizens.

And there's the third option that sort of meets both these opposite extremes in the middle and that's simply recruiting people already within the nation. Given the reported brain drain of the US intelligence forces, getting a substantial fraction of valuable targets (computer scientists, mathematicians, engineers, etc) into positions of intelligence does not seem like it would be all that improbable. Countries like China are already at a major advantage here given the huge numbers of Chinese involved in STEM.