What makes you think Mail::RFC822::Address cannot deal with e-mail addresses that contain non-ASCII characters?

use strict;
use charnames ':full';
use Mail::RFC822::Address qw(valid);
use Encode::Punycode;
use Encode;

my $email_address = "\N{ARABIC SIGN SALLALLAHOU ALAYHE WASSALLAM}" . '
+@' . "\N{CYPRIOT SYLLABLE TA}" . 'be';
my $puny = encode('Punycode', $email_address);
print "$puny\n";
print "That's a valid unicode address\n" if valid($email_address);
print "That's a valid Punycode address\n" if valid($email_address);
[download]

Output:

xn--@be-0we00514a
That's a valid unicode address
That's a valid Punycode address
[download]

Update: added Punycode representation.