Surely this would be so easily done with a few diodes so cheaply
In addition to the real estate issue that kopsis mentioned, there's another problem: diodes aren't perfect conductors. You lose a little voltage between the input and the output. About .7V for the standard power-supply diodes, and about .2V for the more-expensive Schottky diodes.
The "works either way" design requires an arrangement of 4 diodes that results in two diode voltage drops. Losing 1.4V is no big deal when you're powering, say, a radio that can live with 9V off a 12V source. But it's a huge problem if you're trying to charge a 3.7V battery from a 5V input.
The protective circuit would require either raising the input voltage (no more USB sync-n-charge cables) or adding an expensive circuit inside the Z to pump the voltage back up above 5V.
Basically, the designs of PDAs that use 5V adapters and LiIon batteries are right up against the limits of what's physically possible with today's technology. So you can have "cheaply", or you can have "easily", but not both at the same time
Since there's relatively little chance of the average consumer getting the power supply polarity wrong
This, actually, has become a fairly serious problem in an increasingly-gadget-saturated world. There's a voluntary industry standard (from JEIDA) for coaxial power plug sizes and voltages now, but not everybody follows it: And it only partly addresses our problem: there's a
range of voltages for each size, which is mostly okay for radios and cassette players, but not good enough for gadgets that expect a fully-regulated supply. But at least it improves the odds against frying your toys if you mix up your adapters.
Ran