I suspect your mistake lies somewhere else. The above mentioned snipped works as expected and keeps the URL parameters:

#!perl -l
$message_body="http://www.foo.com/bar.pl?aid=3D2744&bid=3D&cn=3DOM=
Ddemo2&rid=3D0";
$message_body =~ s/=([0-9A-Fa-f]{2})/chr(hex($1))/ge;
$message_body =~ s/=\n//g;
$message_body =~ s/=3D/=/g;
$message_body =~ s/>/>\n/g;
print $message_body;
[download]

results in http://www.foo.com/bar.pl?aid=2744&bid=&cn=OMDdemo2&rid=0
While we're at it. the third substitute (the one with =3D) seems unnecessary, as the first substitute already transforms =3D into =.