you only need to check the walls when the water is spreading, and mark the ones that need to eventually dissolve.
We already have the game flag wall tiles as wet, so couldnt we just have a tag that says if wall is 'damp', check surrounding tiles (8 around, and 1 above) for open, water-filled tiles. I personally would then make it a requirement to check if the water is flowing.
Two reasons for this;
1) Solutes dissolve slowly without mixing, because the water immediately next to the salt etc is very concentrated, meaning its difficult for excess salt to dissolve. Flowing water means its constantly adding fresh water, so the concentration of salt in water next to the solid is always low, and the solid salt will dissolve far faster.
2) Rock salt as a mineral is actually a lot more robust than you might think. It doesn't disolve like your nice fine table salt; it's generally been weathered already, and has reprecipitated into large, hard to dissolve crystals. I'm not saying its insoluble, just that it takes a fair bit more effort to get it to do so. As such, the mechanical action from flowing water (and the detritus it carries) helps in breaking up the crystals into a more soluble size.
Then, if everything is satisifed, damage the rock as with mining. Sufficient damage, and the wall goes poof.
Re the city discussion; going back to the obvious circular nature of the cities, couldn't we just delete the roads between the isolated houses? It's not perfect, but it does make the preplanned city shape a bit less obvious.