Almost 20.000 people in my city were killed in a VERY short time and we are still struggling to feed our realm.
To clarify:
Did your city lose 20,000
currently living peasants or 20,000
maximum population?
The former is starvation. The latter is the rebalance. And in nearly all cases, when cities had their populations reduced, it was to help make sure they would not lose more gold due to crime and density effects.
Furthermore, if your city lost maximum population, you should be having an easier time than before feeding it.