Yes, they'll run into scaling to every city immediately, but that happens already with software-only technology.
For example city X decides to change some traffic rule on date Y. Each autonomous vehicle will need to receive an update by date Y. What happens if a vehicle hasn't been updated soon enough?
One solution is a mandatory update scheme. Every day a vehicle checks if it has received its daily update, if not the vehicle is disabled. Another more long term solution could be close co-ordination with cities to determine which upcoming traffic rule changes warrant mandatory (vehicle cannot be enabled without update) updates.
These corner cases may seem trivial, but with zero tolerance for error across hundreds of thousands of cities careful strategies will need to be developed.
I'm curious about what corner cases exist that eg Google hasn't seen in millions of miles driving in a city. [I'm sure there are some, I just don't have a good imagination. Nor can I really fathom what a million miles of city driving is like]