I've had this too. Sometimes whole civs seem to go unavailable as destinations, but only for a while. Sometimes one spy can see everything and another can't. Sometimes, and only sometimes, I can send the spy to a nearby city and then the rest will magically reappear, become visible again, and I can move them on to their true target city.
Not sure what would cause this. I doubt whether it's a policy card held by the target civs that's giving them "Stealth" mode. (If that's the case, I want it!) All I can suggest is that you raise a bug ticket with 2K and include the game save.