Of course we train upset recovery, and that includes possible stall recovery. But the important thing to note is that stall is considered "out-of-control" (quoting Boeing). You are not in control of the aircraft, you are merely doing a series of inputs and then yes, at some point you will be able to recover. A "Cessna-like" philosophy (where you end up with full power for recovery) has created some incidents or even accidents, the most notable one the Turkish Airlines 1951 in Amsterdam. The B737 has limited elevator authority over the THS. If the THS ends up trimming up all the way, there might not be sufficient elevator authority available when you push the engines into full thrust (underwing mounted, they will push the nose up). Hence the aircraft will continue to slide down, tail first, with further on a possible wing drop due to the swept wing design. Since the crash, Boeing changed the recovery procedure and teaches to disregard altitude loss as mentioned by B2N2, focusing on lowering the nose and be patient. Thrust "as needed". We used to do stall recovery to show how little altitude was lost in the recovery, that idea is long gone, we don't look at altitude loss to avoid people focusing on it. We teach to use all the altitude needed for correct recovery.
There are other "SEP" topics that sometimes end up being debriefed in the sim/line training as "no-no-no" topics:
* sideslip to lose altitude
* rudder use (American Airlines 587 crash)
...
(ps: on a SEP, while doing stall excercices, don't you ask students to stop the trim up at a certain point?)