Your analysis of FBW is only partially correct. Not all developers are as careful with ensuring that their aircraft do not depart from controlled flight.
When you're in the vicinity of the airplane's true, aerodynamic "corner speed", your mount will bleed-off energy rapidly. To stay at that corner condition, the pilot needs to exchange altitude for airspeed, or risk stalling his mount. A miscalculation in this could potentially occur more rapidly than the fly-by-wire control system could counteract.
It is for this reason that the flight control laws of the F-16 are more complicated than the "25 degree" AoA limit that you describe. On the F-16A, the flight control laws actually limit AoA as a function of g-load. At 1-g, the FCS will allow up to 25-deg AoA. This maximum is gradually reduced, however, with the system allowing only 15-deg AoA when at maximum g-load. This approach reduces the likelihood that the pilot could bleed off enough airspeed to place his airplane into a deep-stall condition.[1]
You should also be aware that the F-16A and early models of the F-16C had analog fly-by-wire control systems. Later F-16Cs incorporated digital computers. There are differences between the two sets of control laws. However the principals behind them - including how they vary the maximum available AoA - remain the same.
Not all fly-by-wire control systems have applied the approach used by the F-16, however. The FCS for the F-16 was designed to maximize pilot safety, and keep him out of that corner of the envelope where an airplane achieves its maximum instantaneous turn rate, but where it also looses momentum at a precipitous pace. In practical application sustained turn rate was deemed to be more valuable than instantaneous performance. Other developers, however, chose to leave this corner open - so that they could advertise a superior intantaneous turn rate. This leaves more responsibility on the shoulders of the pilot, to ensure that he is aware of the energy state of his own mount. For these airplanes, entering deep stall will be a real possibility, even with a fly-by-wire control system. Similarly, at least one customer has reportedly insisted on the ability to over-ride the AoA limiter on the F-16 - raising the risk of deep stall in real world engagements.[2]
The bottom line is that "deep stall" does happen, even with fly-by-wire control systems. How much you safeguard against it depends on how aggressive the software developers happened to be.
References:
[1] Luat T. Nguyen, et al., “Simulator Study of Stall/Post-Stall Characteristics of a Fighter Airplane with Relaxed Longitudinal Static Stability,” NASA TP-1538 (December 1979), p. 34.
[2] Bill Norton, Air War on the Edge: A History of the Israel Air Force and its Aircraft Since 1947 (Hinckley, England, Midland Publishing, 2004), p. 338.
