4E has made it more explicitly clear that rules need to be applied in light of common sense. If your intent it to try to argue endlessly over a single word in the definition of a power, i'm sure we can be here all year 24/7 before playing a single game.
The intent of divine challenge is for the paladin to offer himself as a mark. As per the rules, he cannot run away, though the rules didn't state it that way. Common sense suggests that becoming invisible as well as teleporting under the floor (but in a square vertically adjacent to the target), phasing through the wall (but in a square adjacent to the target), becoming ethereal, transforming into gazeous form, shape shifting into an ant (effectively disappearing from view unless you have +55 on perception), are all equivalent to runing away even though none of them are explicitly stated in the rules and you could arguably do all of the above according to RAW and still meet the divine challenge criteria.
This is how i would rule this situation:
Paladin: "By my god's power, i challenge you to come and get me!!"
*poof*! (Paladin disppears)
"Hahaha, now you can't seeeee me, now you can't seeeee me, try to fiiiind me!"
Palading moves around the target to hopefully conceal his location. Palading player says to DM that target takes divine challenge damage if he doesn't attack his paladin. DM politely asks player to leave game and never return.
Now if you disagree and want to continue arguing that the RAW says that the paladin met all criteria for divine challenge by becoming invisible (or phasing through the wall or otherwise attacking but then becoming non accessible), fine. Please refer to the infinite oregano counter-argument.
To summarize: if you want to offer yourself as a target, there needs to be a bulleye painted in red on your chest. For all to see. Otherwise, you're not offering yourself as a target.
Sky