In terms of expressing intent, at least in my biased opinion, the original code fragment wins, and the attempts at "making it better" are increasingly obfuscating. Unless performance is a serious issue, clarity of expression should be the goal.

Consider picking up the code blind. Which is easier to understand?

   foreach $oldkey (keys %fdat) {
       if ( ($newkey = $oldkey) =~ s/^redirect_//) {
           $fdat{$newkey} = $fdat{$oldkey};
       }
   }

or

   $fdat{$_} = $fdat{"redirect_$_"} 
       for map { /^redirect_(.*)$/ ? $1 : () } keys %fdat;

I consider myself a pretty fair Perl coder, but I have to admit that it took me an order of magnitude longer to grasp the intent of the second example than it did the first. When I catch folks in my team writing code like the second example, we have a talk. The talk includes asking them to consider the plight of the poor soul who has to pick up the code next.

Clarity, please.