AbdulAlhazred
Legend
Hidden is a huge mess in 4e as witnessed by the 'Rules of Hidden Club' document linked above.
I would have the DM and players work together to figure out something that seems fair.
Cloaked in Shadow is a level 12 Paragon Path power, so it's meant to be reasonably powerful, but not, y'know, EPIC-ly powerful. As a DM I'd probably let this power 'just work' most of the time; I wouldn't try to screw the PC out of his PP.
See, I've never really seen why people call 'hidden' a 'huge mess', its actually QUITE straightforward, by the rules that are published in the Stealth update in PHB2. Some of the sidebars seem to have confused people in PHB1, but the truth is its pretty darn simple.
Hidden is a 'state' that exists between 2 creatures in which one of the creatures is not visible to the other, thus its location is unknown (at least technically, it may well be pretty clear where the hidden creature MUST be). If the hidden creature's current active Stealth result is better than or equal to the passive (or active if it searches) Perception of the other creature, then it is hidden, assuming it abides by the other restrictions listed in PHB2's rules update (or the Rules Compendium, which is worded virtually identically). There are some rules about what allows one to make a Stealth check to hide, and some rules about what will end that state.
Even factoring in invisibility, which brings up the question of being 'unseen' but not hidden, its not THAT complicated. Different senses present some additional rules exceptions when they apply, but even those are relatively straightforward. All one ever needed to do was read the rules and keep in mind what the basic concept was, and it just all works.