Howdy!

A couple of emendations that don't change the essential meaning but do affect whether it works as presented...

my @work = fetch_jobs($starting_condition);
my %seen;
while ( @work ) {
    # Remove 1 item from our stack/queue
    my $job = shift @work;

    # Skip this job if we have already done it
    next if $seen{$_}++; ## $_ should probably be $job, no?

    # Possibly add new jobs to our stack/queue
    if ( more_jobs($_) ) { ## $_ should probably be $job, no?
        push @work, fetch_jobs($_); ## $_ should probably be $job, no?
    }

    # process job
}
[download]

...because $_ isn't set or otherwise given meaning in this snippet.

while ( @work || @work < 1000 ) { # should ought to be && not ||
}
[download]

...otherwise the loop will never exit, as an empty @work will always be less than 1000...