Looking closely at the specific example you gave, I see some repeated work at each return that would give your coworker more reason to fight against multiple returns. I'd probably just factor that out:

sub _foo {
    my( $self )= @_;
    my $authentication= $self->authenticate_user();
    return "Authentication Failed"
        if  ! defined $authentication;
    my $profile= $self->get_user_profile();
    return "User is not active"
        if  ! $profile->is_active();
    my $external_id=
            ( $self->find_external_id($profile) )[0]
        //  $self->send_profile_to_partner( $profile );
    return( '', $external_id );
}

sub foo
{
    my( $self )= @_;
    my( $error, $external_id )= $self->_foo();
    return { status=>0, error=>$error, external_id=>undef }
        if  $error;
    return { status=>1, error=>undef, external_id=>$external_id };
}
[download]

I also question the wisdom of an interface that separately returns 'status' and 'error'. If 'error' is false (including undefined) then the call was a success. An even better interface in the long run is to throw exceptions in the case of failures.