Hi Richard,
Because of the Ajax postback that happens when you expand the tree when Ajax is enabled the js script code doesn't get executed and therefore you don't see the images.
To respond to your questions:
1. I'm not aware of any other way of doing it without js code.
2. Not sure if this can be done without disabling Ajax.
I'd happy to hear other solutions from our customers.