It depends on the trigger of the creature's immediate interrupt/reaction (or opportunity action).
References: see Rules Compendium, page 214-215 - Making Attacks.
An attack is a sequence of 6 steps that I have shortened here.
- Choosing an attack power
- Choosing target(s)
- Making an attack roll
- Compare result against defense to see if it is a hit or a miss
- Apply the effect (damage and/or conditions) described by the power (under hit or miss)
- Repeat 3 through 5 for other targets.
Fighter's Combat Challenge says that:
Every time you attack an enemy, whether the attack hits or misses, you can choose to mark that target.
This could have more than one interpretation. It could be a rider effect of step 3 (because of we don't need to know the result of the comparison). It could be a rider effect of the step 4 (whether the attack hits or misses). It could be also considered part of the step 5 (treating the mark as a riding condition of the power used).
My opinion is that the mark actually is applied on step 4.
Now. Suppose the creature has a power whose effect is...
Case A
The action is an immediate reaction and the trigger is akin to...
Trigger: A creature targets you with an attack.
Effect: You shift 1 square.
The reaction is on the creature being targeted, the attack (step 3) has not been performed yet. The creature has so a chance to escape the Fighter's melee reach, thus becoming a non-valid target and negating the entire attack (along with the mark).
Case B
The action is an immediate interrupt and the trigger is...
Trigger: A creature attacks you with a melee attack.
Effect: You shift 1 square.
The interrupt is on the creature being attacked (step 3), so - in this case too - the attack has not been performed yet. Thus, the creature has a chance to escape the Fighter's melee reach, becoming a non-valid target and negating the entire attack (along with the mark).
Case C
The action is an opportunity attack and the trigger is...
Trigger: A creature attacks you with a melee attack.
Target: Any enemy adjacent to the triggering creature.
Attack: +7 vs. AC.
Hit: 1d8+3 damage.
Opportunity actions interrupt their triggers. The counterattack, in this case, is performed before the Fighter's attack (similar to case B). Thus, Fighter's allies adjacent to him take the attack from a still unmarked enemy (no -2 penalty to attack rolls). After the counterattack is resolved, the Fighter's attack takes place (along with the mark).
Case D
(as suggested by Simon Withers to further clarify)
Similar to case C: the action is an opportunity attack but the trigger is...
Trigger: A creature damages you with a melee attack.
Target: Any enemy adjacent to the triggering creature.
Attack: +7 vs. AC.
Hit: 1d8+3 damage.
In this case the counterattack is performed after the Fighter's attack (step 3), but before damage is applied (step 5). At this point the interpretation on the Combat Challenge feature becomes important: the creature could or could not have been already marked.