If you don't know where the paladin is, you can't very well attack him.
If you don't know where the paladin is, you
can attack him. The mechanics of attacking an invisible enemy are clearly laid out in the PHB p. 281 ("Targeting what you can't see").
Does that make DC/DS not work? No. Notice that -ability- to attack the paladin is not inherent in how the ability operates.
I think everyone in this thread noticed that. That's sort of the point of the thread - the RAW does not make any allowance for paradoxical situations where the paladin is unavailable as a target, and it leads to some bizarre situations. If the creature makes its best effort to attack a paladin, and the attack ends up not including the paladin as a target, then by the RAW the monster takes damage.
I think that's what we're trying to figure out.
Not all Paladins serve gods of honourable combat. I'm certain a Paladin of Sehenine/The Traveler would have NO PROBLEM sanctioning and going invisible. 'But a 3rd edition paladin--' Stop right there. This isn't 3rd edition, paladins don't work that way.
I don't think anybody is arguing that a paladin's class (or class concept) has anything to do with it. Divine Sanction specifically states that the paladin does not have to engage the target; Divine Challenge specifically states that the paladin does have to engage the target. For cases where the paladin vacates the combat, DC is very clear about what happens
after the end of the paladin's turn.
babinro's original question had to do with making attacks where the monster includes (a square in which the monster expects to find) a paladin as a target, but either fails to hit the paladin or hits something other than a paladin. I think the consensus so far has been that trying to hit the paladin and missing is just a miss, but trying to hit the paladin and (even accidentally) hitting something other than the paladin causes the damage to proc.
In your example where the invisible paladin stays adjacent (to keep DC working), let's imagine that the creature has a close blast attack. If he uses the attack as a probe to hit the paladin and the paladin isn't in one of those squares -- but another ally is -- then even if the attack misses everybody, it was an attack that didn't include the paladin as a target, and it procs the damage.
However, if the paladin is using DS instead of DC, and performs some trickery like stepping into Mordenkainen's Mansion or an Arcane Rift to sit out the fight, then there is no way for the creature to include the paladin as a target. Given a typical party's hit points and the damage that DS can deal, that single challenge could cause more damage than any other PC in the fight, because it always hits and the creature will almost certainly continue attacking. DS from a feat-pumped paladin is effectively "ongoing 8 radiant, save doesn't end" against a hostile creature. If you don't think there's anything wrong with that, consider the paladin daily at-will On Pain of Death which deals 1d8 radiant (save ends) after the monster attacks on its turn, or 1d4 radiant (save ends) if it misses.
I'm not saying you're wrong - the RAW seems to support your assertion that the paladin can hide and still zap the challenged target - I'm just saying that there are exploits of the power that boost its potential into the realm of "broken". Adding a DM judgment call on the availability of the paladin as a target seems to un-break these exploits but leaves plenty of room in the gray cases for mild-and-fun exploitation.