It looks like a possible data issue, or just a priority issue. The Fuzzy search service tends to prefer points of interest over geographic locations. This may be the cause.
If you are just looking for cities, I recommend using the V2 search geocoding service and passing your query into the locality
parameter. For example:
https://atlas.microsoft.com/geocode?api-version=2022-02-01-preview&subscription-key={Your_Azure_Maps_Key}&locality={query}
Cities will have a result type of PopulatedPlace
. Trying these with the list of cities you provided works much more reliably.