If you check the perlsub section of the manuals, you get a very brief introduction to the "lvalue" feature. Here is the example:

my $val;
sub canmod : lvalue {
     $val;
}
sub nomod {
     $val;
}
[download]

This isn't terribly helpful, is it? Yet it does illustrate how you are just supposed to leave it there. Perl subroutines normally work such that the last thing left on the stack gets returned, but in the case of an lvalue-enabled subroutine, there must be a special handler that converts the stack entry into a kind of reference which can be assigned to.

Try colapsing your logic into an unfortunately ugly ?: chain:

my %foo;
my $bar;

sub foo : lvalue
{
    my ($key) = @_;

    if (some_complex_condition())
    {
         do_some_stuff($foo{a});
         $key = "b";
    }
    if (other_complex_condition())
    {
         $foo{a} .= do_some_other_stuff($foo{b},$foo{c});
         $key = "a";
    }

    defined($key)?
       exists($foo{$key})?
            $foo{$key}
            : $foo{$key} = undef
       : $bar;
}
[download]

First, figure out what you need to return, taking as much time as is necessary. Then, once you know, shuffle the appropriate variable to the top of the stack and leave it there.