Why would I need to run the code for each directory separately? Isn't that the whole point of recursion, so it will drill down into each directory until there are no more levels?

MatchDirs is not doing what you think - it is not saying "if a directory matches this pattern go in and recurse". What it is saying is "for every directory do not enter unless its name matches this pattern". Changing the pattern will not help as it tests against the directory name not the path.

Peeking into the Module's relevant code may help:

elsif ( $file->is_directory() ) {

    if( (     $options{MatchDirs}
          and $filename !~ $options{MatchDirs} )
        or
        (     $options{OmitDirs}
          and $filename =~ $options{OmitDirs} )){

        next FILE;
}
[download]