What OS are you using? Are you sure the OS version of rmdir is being found, and not some rogue application that's pretending to be rmdir? Running

perl -e "my $cmd = qq(rmdir /s /q TempDirTree); print `$cmd` . qq(\n)"
[download]

from the command line works as expected for me using Vista64 and ActiveState Perl 5.8.7.