The moment you stall, you lose altitude, and you're no longer in the coffin corner.
The moment you stall, you are outside the flight envelope which includes that corner. You remain outside until you recover from stall. Losing altitude is not a stall recovery technique. Restoring laminar flow over the wing is. That may involve sacrificing altitude for airspeed, assuming you still have enough elevator authority to reduce AOA. Another method is to use excess thrust, assuming it is available at that altitude (the higher you are the, less available.)
A simple stall recovery, and you're back in normal flight.
Stall recovery in large swept-wing aircraft at cruise altitude is anything but simple. It requires a great deal of patience and energy management to avoid secondary stalls. Once recovered, you remain in alternate or direct law- no more normal law until on the ground and reset.
The A320 in particular is designed so the computer will automatically recover from stalls if the pilots simply release all controls.
Untrue. When you stall an A320, you revert to alternate law (hopefully with speed stability), as normal law will not let you stall. If you stalled, something went wrong. The flight control computers are saying essentially that "I cant fly the plane anymore- you the pilot must do it." It will not recover without pilot intervention.
...one of the pilots on AF447 kept directing the plane to pitch up without telling the other pilot what he was doing, as the other pilot was trying to pitch it down to recover from the stall
This did happen, and they were disoriented but not stupid, just poorly trained. The aircraft also gave them a "dual input" aural warning and averaged their inputs. The first sense to disappear when under stress is hearing. They were under stress and poor training in stall recovery left them unable to prevent secondary stalls. This was one of many other factors to this particular accident as well as all accidents in general.