But that seems inelegant. Is there a more elegant way?

Yes, wrap it in a sub

if( my $lastname = uid_lastname( \%uid, 'Alice' ) ){
    print "lastname is $lastname\n";
}
[download]

sub uid_lastname {
    my( $uid, $firstname ) = @_;
    my @lastnames;
    keys %$uid;
    while( my( $key, $val ) = each %$uid ){
        if( $val->{firstname} eq $firstname ){
            push @lastnames, $val->{lastname};
        }
    }
    return @lastnames if wantarray;
    return $lastnames[0] if @lastnames;
    die "firstname not found";
}
[download]

Other "elegant" options might include Data::Diver , Data::DPath, Data::Path/Data::Path

update: with dpath you can lookup the lastname like so

my $lastname = dpath( q{/*/firstname[ value =~ /Alice/i ]/../lastname}
+ )->match( \%uid ) 
my $lastname = dpath( q{/*/firstname/.[ value eq 'Alice' ]/../lastname
+} )->match( \%uid ) ;
[download]