Is my zener diode labeled wrong, or am i seeing a strange failure mode?

The black ring on the Zener should typically be the same as the "bar" on the schematic. However, weird manufacturers may do weird things. Have you checked the markings on the Zener to the data sheet? What brand and model Zener is it?

Overvolting a Zener and letting out the magic smoke will typically just make it short out, it won't "reverse" the direction of it.

Note that the circuit shown is basically just building another (simpler) voltage regulator to burn off the voltage seen by the Zener. If you want to go from 40V to 5V drawing more than a few milliamps, you probably want to use a switching buck converter, rather than a linear regulator, to avoid generating 8x as much heat in regulation as you actually put out as useful regulated current/voltage.

The behavior you describe reproduces in the simulated circuit exactly. If we configure the Zener to a 25 reverse voltage and have it in the circuit the right way, Q1 drops around 25V. If we reverse the Zener, we get approximately two junction drops, as you found empirically. So it looks like you have the right circuit, and that the Zener is marked wrong. The stripe on the diode should correspond to the cathode bar on the schematic.

A long-standing rumor is that NTE buys other manufacturers' semiconductors and stick their own name and their own NTE-specific part numbers on them, possibly after testing the parts to figure out what they are. Maybe your diode came from a batch that ended up as NTE because they were marked backwards.