Forget not knowing about the mark, not knowing about the effect of the entire power.
Alright. Divine Challenge does NOT say 'You must attack the paladin' per se. You can use a utility power, or any power that does not attack anyone, and have no problem.
What it does do is punish you for attacking those that aren't the paladin without -also- attacking the paladin.
So let's say I AoE where the Paladin is invisible. I'm targeting the paladin so no damage.
I target a square with a ranged or melee power with the intent of smacking down the source of the Divine Challenge power. Is the Paladin in that square? No? Then I ask another question. Is -someone else- in that square? If yes, I take damage, because I -am- targetting with an attack that doth not include the paladin. If no, then damage, because you're attacking the square, and if you miss, the miss effects happen -to the square- (in other words, to nothing)
Think of it this way. You're making an attack, the powers that be go 'THAT ATTACK GOING IN BAD DIRECTION, NOT WHERE PALADIN ARE' and punish you accordingly. Intent doesn't matter, because if another invisible bloke were in that square, you'd have taken damage. Divine Challenge does not care about who you hit with an attack, only that you made one, and that it wasn't the paladin in that party.
And lastly, 6 paladins can't hit the same target with Divine Challenge damage because the damage trigger only exists while the target is marked by you. Any effect that ends the mark ends the damage-trigger.