I don't think you are going to get a much better than tweaking the hash solution unless your data is rather nice and can use Limbic~Region's method. I did try another way (build a regex containing the required substitutions and eval it against the data), more to prove it was a non starter than because I thought it would be faster. Code and benchmark for a laugh.

#!/usr/bin/perl
use warnings;
use strict;
use Benchmark;

sub simple_hash {
    seek DATA, 0, 0;
    while (<DATA>) {last if /^Names/}
    my %lookup;
    while (<DATA>) {
        next if /^\s*$/;
        last if /^Example List/;
        chomp;
        my ($first, $second)=split;
        $lookup{$first}=$second;
    }
    while (<DATA>) {
        next if /^\s*$/;
        chomp;
        my ($name, $rest)=split /\s+/, $_, 2;
        print $lookup{$name}, "\t", $rest, "\n";
    }
}

sub funky_regex {
    seek DATA, 0, 0;
    while (<DATA>) {last if /^Names/}
    my $regex_string="";
    while (<DATA>) {
        next if /^\s*$/;
        last if /^Example List/;
        chomp;
        my ($first, $second)=split;
        $regex_string.="s/$first/$second/;";
    }
    local $/;
    $_=(<DATA>);
    eval $regex_string;
    print ;
}

timethese(5000000,
    {
        'simple_hash' => &simple_hash,
        'funky_regex' => &funky_regex
    }
);

__DATA__
Names
Guido Meyer
Mike Smith
Klaus Rothschild
Mick Mouse
Daffy LeCannard

Example List
Guido bla1 ...
Mike  bla2 ...
Klaus bla3 ...
Mick blahsome more
Daffy lookout Duck !

# results
funky_regex:  0 wallclock secs ( 0.30 usr +  0.00 sys =  0.30 CPU) 
    @ 16666666.67/s (n=5000000)
            (warning: too few iterations for a reliable count)
simple_hash:  0 wallclock secs ( 0.01 usr +  0.00 sys =  0.01 CPU) 
    @ 500000000.00/s (n=5000000)
            (warning: too few iterations for a reliable count)
[download]

Cheers,
R.