FWIW (since I no longer write Perl for a living) I consider loop labels to be the exception rather than the rule. This means I use labels only if they are necessary. My take on your code example would be:

OUTER:
for (...) {
    next if $cond1;

    for (...) {
        ...
        last if $cond2;
        ...
        next OUTER if $cond3;
        ...
        last OUTER if $cond4;
        ...
        next if $cond5;
        ...
    }

    last if $cond6;
}
[download]

I find that this makes it stand out when something unusual is going on, in a way that labeling everything obscures.

One counter-argument to my position is that labeling everything and using the labels everywhere makes it explicit where all the control transfers go.

I believe the arguments against ever using labels have already been adequately covered (deeply-nested control structures, flag variables that must be carried around and tested, etc, etc ...)

The bottom line is that there is no magic bullet, despite the touching faith of certain people in the $work environment to the contrary.