A similar issue was discussed recently in unicode problem with Email::Valid; McA has good information and tips in Re: unicode problem with Email::Valid. The short version: use Encode;, and then decode your data as MIME-Header (and encode the same way it when you'd like to go the other way).

#!/usr/bin/perl

use feature qw/say/;
use warnings;
use strict;

use Encode;

say decode('MIME-Header', "=?iso-8859-1?Q?=C3=BC =C3=B6 =C3=A4?=");
[download]

Output:

$ perl test.pl
ü ö ä
$
[download]

I tried the above example provided and it works perfectly fine.
But when I tried the below it fails.

#!/usr/bin/perl

use feature qw/say/;
use warnings;
use strict;

use Encode;
#assuming that my message is stored in some variable called $str
my $str="Wir freuen uns, dass Sie den 1&1 E-Mail-Service f=C3=BCr Ihre
+=20";

print decode('MIME-Header', "Wir freuen uns, dass Sie den 1&1 E-Mail-S
+ervice f=C3=BCr Ihre=20");
print "\n";
print decode('MIME-Header', "=?iso-8859-1?Q?".$str);
[download]

Thanks
Arun

Don't forget the trailing ?=:

#!/usr/bin/perl

use feature qw/say/;
use warnings;
use strict;
use Encode;

my $str = "Wir freuen uns, dass Sie den 1&1 E-Mail-Service f=C3=BCr Ih
+re=20";

say decode('MIME-Header', "=?iso-8859-1?Q?" . $str . "?=");
[download]

Output:

$ perl 1092761.pl
Wir freuen uns, dass Sie den 1&1 E-Mail-Service für Ihre
$
[download]