As an alternative to the use of armies to hold squares for an indeterminate period of time to mark an intention to settle or exodus a city to a location, the game could offer advanced messengers that would allow a player to leave a message on a square stating their intentions and time-frame.
I agree that it is annoying to exodus a city, send it on a 7 day journey only to find someone has moved in nearby to the new location.
But, I have also seen rampant greed on the part of players with armies being rotated to mark squares for over a month, I have seen one player mark 3 squares for over 4 months as they tried to plot out their entire empire.
My attitude is why should other players suffer for someone else's greed? The advantage that an advanced messenger could offer is to clearly state that "Player X has a city arriving at this location on XX/XX/XX date". If the time-frame is reasonable then other players will respect it. If not, then the messenger will no doubt meet an unfortunate end.