In choosing a power supply it's not simply about damage to the PICAXE or chips but what secondary damage may be caused.
I think the main difference between a PC PSU and batteries, and what gives rise to cautions with use of the PSU, is the potential damage that can be done which can be far greater. A PC PSU can put out enough current to burn tracks of PCB's and even melt its own supply wires and still not fail under shorted conditions.
It's true that some batteries can deliver high currents and may even explode or catch fire under short conditions but that's not so likely with alkaline batteries which would be recommended over rechargeable and other high capacity batteries.
To protect from reverse connection of power supply one can use blocking diodes, or regulators which have reverse voltage protection. One can use crowbar diodes but those may appear as a short with consequential problems described above. The simplest safety measure is probably to use polarised power connections and to take care otherwise.
Protecting from over-current can be harder. Even with a current limited bench supply it's hard to set a level which allows normal operation and worse case current while preventing damaging over-current in a part of the circuit. If you need 100mA to allow a PICAXE to drive a LED, a 100mA limit won't save a PICAXE delivering 100mA through a leg shorted to 0V when the LED is off.
A fuse has the same problem; that it only blows when current exceeds its rating. That might protect from dead shorts and some faults but not all.
Self-resetting fuses can bring their own problems as well; as anyone who has been following the saga of using those on a certain fruity-flavoured development board will have seen. The design used was apparently intended to provide over-voltage and reverse voltage protection yet seems to provide neither, while the over-current fuses have caused various operational problems.
Ultimately there is no way to entirely protect a circuit unless it lends itself to a particular protection regime and it would be likely that most circuits will not. In the absence of a guaranteed protection regime the best anyone can do is use a supply which has least consequences should things go wrong.
On the safer side we have current limited bench supplies, then alkaline batteries, followed by rechargeables which shouldn't catch fire or explode, then those which can and other high current supplies that could present fire risks and similar.
Obviously the safest solution would generally be recommended as it's about minimising risks. There's no prohibition on using any supply but, for the general case, it would usually be better not to use those with more potential for harm.
