My first thought was autonumber, but obviously that won't do.

It seems to me that for this to work you will need to track the highest used number for each city. That being the case, the obvious way to do so would be to add a table to the database (depending on your design, this may be as simple as adding a field, if the cities are in a table already) that keeps the max number for each city.

I would want to encapsulate the number recovery in a function or two. Perhaps a SaveMaxNumber(cityName as string) and GetMaxNumber(cityName as string) as integer