I'm going to get very verbose here to put this to bed for myself and my players.
The text of Divine Challenge on the character sheet from KotS reads:
Effect: You mark the target. If the creature was already marked, you mark supersedes the previous one. The target remains marked until you use this power against another target, or if you fail to engage the target (see below). A creature can be subject to only one mark at a time. A new mark supersedes a mark that was already in place.
The text from the PHB reads:
Effect: You mark the target. The target remains marked until you use this power against another target, or if you fail to engage the target (see below). A creature can be subject to only one mark at a time. A new mark supersedes a mark that was already in place.
In both cases the "see below" text reads:
On your turn, you must engage the target you challenged or challenge a different target. To engage the target, you must either attack it or end your turn adjacent to it. If none of these events occur by the end of your turn, the marked condition ends and you can't use Divine Challenge on your next turn.
You can use Divine Challenge once per turn.
Taking the PHB version as an authority and breaking it down logically:
1) You mark the target.
- done. the target gets a mark
2) The target remains marked until you use this power against another target, or if you fail to engage the target.
- ok. we know that the mark is persistent and what conditions end the mark: either it's used on someone else or the character fails to engage.
- the definition of "engage" is simple: attack your target or end your turn adjacent to it. (this power can be tough to use against Dragonshields as they can shift away after a move action but before the attack, hence negating the mark and leaving the Paladin unable to Divine Challenge next turn. Since Divine Challenge is a minor action, players should try and remember to use it after they've moved to minimize this.)
3) A creature can be subject to only one mark at a time.
- this qualifies as another way the mark can be removed, but (IIRC) it applies to all marks all the time. Any given creature can only ever have a single mark.
To summarize, the Paladin can Divine Challenge and leave that creature marked as long as he engages it every turn. If he fails to engage, the mark disappears.