maybe locking the variable before I update it? I was thinking that each thread is updating a different hash key of the variable, so it should be safe to update this way? Or does it need to be locked before each join statement?

All your updates to %Found are done within the same thread, so there is no need to lock anything. Besides which %Found isn't a shared variable, so you couldn't lock it if you tried.

Any suggestions on how to do this better?

Apart from this:

foreach my $dir ( sort keys %Found ) {
   foreach my $item ( sort @{ $Found{$dir} } ) {
     push(@Final, $item);
   }
}
[download]

Could be more efficiently written as:

foreach my $dir ( sort keys %Found ) {
   push(@Final, sort @{ $Found{$dir} });
}
[download]

Not really. It is hard to see any scope for you not getting all the results produced by the external commands.

Perhaps you could print out the size of @results before returning and then sum those and compare it with the size of @Final?