As I've often posted about, I find doing overland travel well a challenge (of my GM skills!), including in 4e.
The issues I have with some standard approaches are:
* Extra combats can be boring, and I don't like boring as the penalty for failure;
* Getting lost or similar stuff can have the same problem of being boring;
* Fatigue or similar sorts of numerical penalties can produce a death-spiral type effect upon arrival (the "can" is deliberate - this isn't inevitable, but is an issue I've had).
In 4e in particular there is also an issue with making a
harder combat the consequence of failure - a harder combat gives more XP, and so isn't any sort of penalty, and depending on the context may be more enjoyable/interesting than an easy combat - so why gate it behind failure?
Here are some things I've had success with (in 4e and BW):
* Upon arrival, the fictional situation is different from what was expected/hoped for (eg after a desert crossing, the first well has been fouled by an enemy);
* Getting lost or something similar changes the fictional circumstances of arrival (eg the PCs arrive on the other side of the river/gorge from where they need/want to be);
* Resources are depleted - this can include not having been able to take an extended rest while travelling due to non-restful conditions.
With depleted resources, there is the potential for death spiral but in 4e at least I think that limiting access to resources works better as a type of penalty (if only because it makes the players sweat a bit more while not actually death-spiralling them given their depth of resources, at least above very low levels) than does imposing numerical penalties to actions, which can start to destabilise the maths.
Ultimately I think that, in the context of 4e, having the fiction change in some adverse/undesired way is generally better than mechanical penalties or hurdles. (In BW it's different because while penalties can produce a death spiral they can also make it easier to get checks at the difficult needed to improve character abilities - whereas there is no analogue to that in 4e.)