Just to add my 2 cents:
This isn't magic: the gathering. In that game, cards that become invalid targets are no longer affected by the original spells/enchantments.
As far as I remember, in DnD, targetting is checked at casting time only. I never read anything different in any sourcebook.
So, for the Hold Person question: In my opinion, once the human fails his save, it doesnt matter what he polymorphs into, he still has an active Hold Person spell on him. (Of course, this doesn't answer the question of whether a non-humanoid with an active Hold Person spell on him still suffers from the effect. This might be open to a little interpretation. I dont have the experience to rule on something like this, so if I were dm'ing, i would simply side with whatever is best for the player.)
For the Shillelagh question: The staff was a valid target when the spell was cast. So, you are holding a non-magical staff with an active Shillelagh spell on it. This spell happens to give the staff new properties, but you are still [technically] holding a non-magical staff with an active shillelagh spell. For example, if you add "Magic weapon" - the cleric spell - this doesnt make the shillelagh spell go away.