Dross
Explorer
Far as withdrawing...that's the funny thing about reach. A lot of big monsters I've seen DMs play will try to charge in and attack at the extreme of their reach, but in fact it's often better to move in close.
If using the Charge action then you must strike as soon as you can attack, which means at reach if you have it (I'm sure you knew but just saying). But yes, other than that moving up to limit withdraw actions is a good idea in most cases.
As for the OP:
I agree with the others saying that AoO's recharge on the creature's turn.
I agree with the others saying that the AoO's shouldn't change mid-encounter. The timing of the requested rule check would annoy me, as it appears on the surface like the player is happy for the rule until it inconveniences him but okay at other stages.
As for the undead tree, I don't mind the way FranktheDM suggest to run the spell