Personally, I think early return is lazy programming because not cleaning up non-RAII objects is only one class of bugs that it can introduce. Things like vector renormalization, update notification and even later sections of algorithms can all be missed by early return. Not having early return means you need to explicitly skip later code if you don't want it, rather than essentially turning on "skip-all".
* (Classic): use goto so that instead of returning directly, all branches jump to a cleanup label. This is tricky to do well, but possible.
* (Nonstandard): GCC offers a nonstandard function attribute to register a function as a destructor for this kind of thing. I'm sure they claim it was inspired by Scheme's dynamic-wind/dynamic-wind concept.
* (Memory pooling): Apache APR relies heavily on memory pools. One feature of APR's memory pools is the ability to register functions to run (in, I believe, non-deterministic order) on data when the pool is eventually destroyed.
Containers and resource handles are Stroustrup's advice in his blue C++ book.
Manual deletion is something I would never really want to see outside a destructor.