This has not been my experience either after many games. Maybe a small rules error in your play? Just curious as I have found taking Stalingrad very challenging as mentioned above.
Nearly every time I have played I have been able to take Moscow or Stalingrad without much problems even with them fortified. Usually because I can get 4 units around the city and with about a 50% chance of drawing a green with in one or 2 turns they fall.
I have gone to the stage of saying that a German attack via a major city is like Axis Allies attack no effect if Green X or *.
Just playing the Flau Blau scenario I am in summer 1944 with the Germans holding Grozny and still just infront of each Soviet major city.