map {
   s/.../.../seg;         <-- Escapes the index.
   $form_data{$_} =~ ...  <-- Should be using unescaped index.
   ...
}

##</code><code>##

$form_data = join '&',
             map { my $key = $_;
                   my $val = $form_data{$_};
                   $key =~ s/([^A-Za-z0-9])/sprintf("%%%02X", ord($1))/seg;
                   $val =~ s/([^A-Za-z0-9])/sprintf("%%%02X", ord($1))/seg;
                   "$key=$val" }
             sort keys %form_data;

##</code><code>##

use URI::Escape qw( uri_escape );

$form_data = join '&',
             map { my $key = uri_escape($_);
                   my $val = uri_escape($form_data{$_});
                   "$key=$val" }
             sort keys %form_data;

##</code><code>##

use URI;
use URI::QueryParam;

my $uri = URI->new(...);

$uri->query_param($_ => $form_data{$_})
   foreach sort keys %form_data;