The big thing affecting recovery from a stall at high altitude is that there is very high drag at such low speed, and little thrust available from the engines due to the low air density. You need to descend to allow the speed to increase. In the high altitude flight testing I've done on transport category aircraft (various business and regional jets), it usually takes a descent of 2000 ft or so to build enough airspeed so the drag is low enough to allow the available thrust to be sufficient for a reasonable acceleration.
At 20,000 ft, the engines have much more thrust available, so it should be possible to recover from the stall with less than 1000 ft altitude loss, assuming a sharp pilot (but a sharp pilot should never have stalled in the first place, so we can't assume he suddenly becomes razor sharp during the stall recovery).
All the stalls I've done on large airliner types (various Airbus products, in direct law, to confirm Airbus's claimed CL Max value) have been at lower altitudes, but the same should apply to them at high altitude. The interesting thing about aerodynamic stalls in the Airbus is that from the perspective of the pilot's seat it is very difficult to identify the moment when the aircraft stalls. Light buffet starts prior to the stall, but there is no aircraft wing drop or nose down pitch to identify the moment of the stall. We relied on the flight test engineer in the back, who was monitoring the output of the flight test instrumentation, to call out "CL Max", as the point to initiate the recovery.
Note: all the above comments are with respect to an aerodynamic stall - i.e. the angle of attack has exceeded the value for maximum lift. If the pilot recovers at stall warning the drag is somewhat lower, and thus less altitude loss is required for the recovery.