See Dan Ramsey's message to geowanking.
This service is a substring match searches the textual descriptions of the cities. You can also get cities within a certain radius of another city, e.g. http://swordfish.rdfweb.org/discovery/2003/11/cities/nearcityxmlrdf.jsp?query=amsterdam&radius=0.2
return RDF/XML
return RDF/XML, exact (but case insensitive) match
return Ntriples