The output will not be sent to the terminal until foo actually outputs it. If you want to see it more in depth, I suggest a slight modification to your program following the Unbelievably Obvious Debugging Tip by dreadpiratepeter:

tee('foo');
tee('bar');
tee('baz');

while (<>) { print }

sub tee {

    my $key = shift;

    # reopen STDOUT in parent and return
    return if my $pid = open(STDOUT, "|-");
    die "cannot fork: $!" unless defined $pid;

$|++;

    # process STDIN in child
    while (<STDIN>) {
            chomp;
            print "$key: <$_>" or die "tee output failed: $!";
    }
    print "$$ exiting...\n";
    exit;  # don't let the child return to main!
}
[download]

You'll notice that it's exactly as you told: parent is talking to baz, which is talking to bar, which is talking to foo. But each one prepends its name, so you end up with the reverted list.