1. Different minimal lengths of region codes
2. Different maximum lengths of region codes
3. It sholud find those values on it's own

Update But... it's all there already ?
There are no string comparisons, and the order of look-ups assures that the longest existent key/prefix always win.

Oh, it's not, I just misunderstood your points. But definitely not hard to add, if really needed:

use List::Util;

my $min_prefix_length = min keys %prefixes;
my $max_prefix_length = max keys %prefixes;

my $prefix_length = $max_prefix_length;

while ( $prefix_length-- >= $min_prefix_length) { 
    last if exists $prefixes{ substr( $phone, 0, $prefix_length) };
} 

# Error/inexistent prefix if $prefix_length < $min_prefix_length;
[download]

etc.