Also, for example, when you have lots of "if" clauses, those languages force us to use mutable state (and a variable initialized as null) just to avoid early exits. But we can avoid both by treating the "if" as an expression, as in Ruby, Lisp, etc, or with the ternary conditional operator...
Plus, IMO, there are some situations where early exits are a good idea even in languages derived from C, such as with guard clauses/preconditions.
There's a nice discussion about that here with some points I made: http://c2.com/cgi/wiki?SingleFunctionExitPoint
(EDIT: I edited a lot but still couldn't make it clear that I agree with you, but I still ended up making points about completely different things, sorry about that, my english skills are lacking sometimes)
Even less bad in C++ where destructors can automatically handle any cleanup (exactly that is also common practice in C++; making the cleanup implicit). Similarly in many other more high level languages with GC and/or automatic refcounting or so.
In rare cases, it might be more complicated, though.
But you seem to have some languages in mind where it really doesn't matter? What languages?
I believe that the majority of programmers agrees that using early returns for guard clauses is an okay exception.
As a general piece of advice, this is flat out wrong. Or, to put it more correctly, this is only valid advice when using certain languages and only under certain conditions. Just because it is sound advice in languages with C/C++ derived syntax doesn't mean it should be presented as good advice in general.