Yikes. Lots of return points have always felt like a code smell to me. I've found that it tends to create surprising and frequently hard-to-maintain code. I do use early returns somewhere, but I'm rarely happy about it.

For things like the first example, why not something like (in Ruby):

    # Returns a cached user object either by their user_id or by their username.
    def get_cached_user(user_id = nil, username = nil)
        user =  cache.get_user_by_id(user_id)        ||
                cache.get_user_by_username(username) ||
                db.get_user_by_id(user_id)           || 
                db.get_user_by_username(username)    ||
                raise ValueError('User not found')            
        cache.set_user(user, user.id, user.username)
        return user
    end

You just try all your getters, cheapest first, and when the getter returns a nil or false value, the next one will be tried. Once one is found, no more are tried. Then you just set the resulting value in your cache and return the value. One return statement, no ugly nested ifs, and your unnecessary statements never evaluate, which is what you want anyhow.