Total agreement with your suggestions -- just wanted to add that the "print_all_nicknames" function would be easier if there's a hash of arrays built from the original "%formal_name" hash:

my %formal_name = (
    bill => 'william',
    will => 'william',
    willie => 'william',
    billie => 'william',
    bob => 'robert',
    bobbie => 'robert',
    ...
);
my %nick_names;
for my $nick ( keys %formal_name ) {
    push @{$nick_names{$formal_name{$nick}}}, ucfirst $nick;
}
...
print_all_nicknames( 'William' );

sub print_all_nicknames
{
    my $formalname = lc shift;
    if ( exists( $nick_names{$formalname} )) {
        print ucfirst $formalname, " has these nicknames: ", 
                 join( ", ", @{$nick_names{$formalname}} ), "\n";
    }
    else { print ucfirst $formalname, " has no nicknames.\n"; }
}
[download]

(updated to fix sub name -- and to add missing curlies, as pointed out below by toolic)