Determining how similar a given string is to a collection of strings
Some better statistics to think of are word length and $n$-gram analysis. For word length, you can collect statistics of the distribution of word length of city names, and compare it to the length of what you get. $n$-gram analysis looks at the distribution of sequences of $n$ letters in your sample text (say $n=2$). Both approaches can be combined.

Given the heuristics, you can use likelihood to get a score which would (hopefully) be higher for your sample data than for other text. In order to determine a reasonable threshold, you can perform cross-validation. Pick a set of sample phrases which are not city names. Divide the city names into two parts, a large (say 80%) part and a small (say 20%) part. Train your model on the large part (that is, collect statistics on the large part), and then evaluate your model on the small part and on the sample of bad phrases. Determine if there is a reasonable threshold that passes most city names, but only a small amount of bad phrases.