The total velocity unfortunately mostly downward was enough to fly and create lift, if they only where able to get the nose down in the flight pass direction.
Either the information provided by the BEA is inaccurate, or I have forgotten my trig, or there is a persistent misunderstanding on this thread about the attitude and flight path. The BEA report says pitch is 16 degrees nose up, 35-40 degrees angle of attack, and 10,000 fpm down. To get the flight path angle, you subtract the angle of attack from the positive pitch angle, giving around -20 to -25 degrees. The true airspeed is 10,000 fpm, or around 100 knots, divided by the sine of the angle, which gives around 250 knots. The airplane was in a stalled, mushing descent, not a vertical plunge or falling-leaf type of maneuver. At least this is what the BEA numbers require.
It appears to me -- with zero experience of flying this type of aircraft -- that recovery would not have required a great deal of height, once the wing was unstalled by trimming the THS and getting the pitch angle into the vicinity of the flight path angle, ie 20 degrees or so below the horizon.