The problem is that you have to loop over the whole hash to know that a username wasn't found. You could do it like that:

my $found = 0
foreach my $key (keys %name_hash) {
      if ($key =~ m/$_/i) {
               print "The username is $username and the password is $p
+assword, please enter another name to search\n";
               $found = 1;
      }
}
if (!$found) {
    print "I'm sorry, there is no one here by that name, please try an
+other name or type exit to end.\n"
}
[download]

(there are better ways to achieve case insensitivity, but it's a start).

Another hint: your code will only store the last username and password that was entered. Do you know why?