The situations you outline only come into play if you are reading the rules strictly literally. And, if you're reading the rules literally, attempting to attack an inviisible paladin who has marked you means you take Divine Challenge damage under all circumstances, so the situations you outline can't come into play.
Which means that your options are clear - either refrain from attacking altogether, or attack someone else and suck up the penalties. Or find some way of trying to guess where he is, like scattering a bag of flour around you or something. It is not possible to actively declare that you are trying to attack him because you cannot even designate him as a target, even with area-affecting powers. The best you can do is to hope that you catch him in the area blast, but by that time, it is too late - you will already have suffered the drawbacks, which is not retrospective in nature (in that you do not heal damage if you end up actually hitting him).
If, on the other hand, you're attempting to play by the spirit of Divine Challenge, regardless what the literal wording might say, and rule that making an attempt to strike the paladin doesn't draw challenge damage, then you would also rule that such an attempt must be made in good faith. Thus, you cannot claim "I think the paladin is beside the wizard" when you know he is not beside the wizard. Ergo, the situations you outline can't come into play.
Then let me rephrase my earlier point.
Now that the paladin is invisible, he could, in theory at least, be anywhere. While it is likely that he isn't too far away from the last square he occupied while he was still visible, it is not impossible that he may have somehow moved near/adjacent to a PC I happen to want to attack. While you can certainly suspect that such an event is highly unlikely, you cannot dismiss it as utterly impossible, because by definition, you cannot see him, and thus cannot possibly know whether you have managed to attack him or not with your area attack until it has actually been made.
In short, you're presenting a situation where we ignore the literal rules, but then use the literal rules to manipulate the situation to an unfair advantage. That's called hypocrisy, and no ruleset can overcome that sort of attitude.
I don't see where I am ignoring the literal rules. My point is exactly that - unless the monster in question has some way of defeating an invisible foe, than there is really no way you can overcome divine challenge+invisibility using conventional methods. They just interact that well together.
Does this make said combination problematic? Perhaps. Does this mean my interpretation is flawed? Again, not necessarily. I have always believed that an argument should not only be correct, but that it should also be correct for the right reasons. Claiming that my explanation is wrong because it appears overpowered just means that a houserule may be in order in your games (and your games alone). After all, no one disputes the seal of binding+regeneration combination even though it clearly lets you 1-shot a lv33 solo brute. I don't write the rules, I merely interpret them to the best of my capabilities.
Nor do I particularly agree that the "intent" of divine challenge is to force the paladin to assume a melee combat role, or that you are not supposed to mark-and-run. The way divine challenge is worded seems to allow exactly that!
The problem with this is that it only appears to work for lawful paladins who actively engage in melee. As pointed out, it is certainly not impossible to build a ranged paladin, such as a halfling paladin who taunts his foes from a distance and frustrates him by mainting his distance and using other evasive maneuvers whenever said foe tries to get near him. After all, the paladin is still facing him in combat. He just never said that it would be easy to locate and take him on.
