Two changes fixed this:

sub search_dir{
    my $sub_name = shift;
    local *SUB; # <---- 1st: In order to have a new *SUB for each recu
+rsion...
    opendir SUB, $sub_name or die "Couldn't open the specified directo
+ry: $!";

    while(my $file = readdir(SUB)){
        next if $file eq "." or $file eq "..";
        next if $file eq "output.txt";

        $file = "$sub_name/$file"; # <---- 2nd: since you didn't chdir
+...
        print $file, "\n";

        if(-d $file){
            search_dir($file);
        }elsif($file =~ /\$\$/){
            print OUTPUT "Possible \$\$ file found: $file\n";
        }
    }
    #close SUB;
}
[download]

As ikegami already said, File::Find is your friend.