Playing as Cyrus, I am only able to send spies to my own cities and Macedon's (the last civ I encountered on the map, if that might be the reason why).
However, I CAN send a spy to a city of another AI if I click on the "Travel To New City" option if it is the first time I have done so since I loaded the save. If I click on that button for the first time since loading that save (which shows all known cities as it is supposed to) then either clicking on a city on the list then click "CANCEL", or closing it then reopening it, only the cities owned by Persia and Macedon show up. This forces me to dave and reload each time I need to send a spy to a non-Macedonian city.
However, I CAN send a spy to a city of another AI if I click on the "Travel To New City" option if it is the first time I have done so since I loaded the save. If I click on that button for the first time since loading that save (which shows all known cities as it is supposed to) then either clicking on a city on the list then click "CANCEL", or closing it then reopening it, only the cities owned by Persia and Macedon show up. This forces me to dave and reload each time I need to send a spy to a non-Macedonian city.