This might serve as a starting point.

#! perl -slw
use strict;

sub genRegex {
    my $query = shift;
    $query =~ tr[A-Za-z0-9 ][a-za-z0-9 ];
    my @words = split ' ', $query;

    my $regex = join '\W+'.$/, map{
        my $s='';
        $s = "(?:$_$s)?" for reverse split '';
        chop $s;
        "\\b$s\\b"
    } @words;
    return qr[$regex]xi;
}

my $regex;

while( my $line = <DATA>  ) {
    chomp $line;
    $regex = genRegex( $1 ) and print'' and next
        if $line =~ m[search for (.*) should match...];

    print +($line =~ $regex ?  'Matched ' : 'Failed  ' ), $line;
}

__DATA__
search for Aetna Insurance Company should match...
Aetna Insurance Company
Aetna Ins. Co.
Aetna Insurance Co.
Aetna Ins. Company
Aetna Ins Company
aetna insurance co
Aetna Ins Co
Atna Insurance Company
Aetna Ins. Ca.
Aetna Insurance Go.
Aetna Ins. Compary
search for Sam Jones should match...
Sam Jones
Sam J. Jones
Sam J Jones
S. Jones
Samuel Janes
Sam L Jones
Sam J.J. Jones
Sam J Jones
B. Jones
Manuel Jones
[download]

Results:

P:\test>junk

Matched Aetna Insurance Company
Matched Aetna Ins. Co.
Matched Aetna Insurance Co.
Matched Aetna Ins. Company
Matched Aetna Ins Company
Matched aetna insurance co
Matched Aetna Ins Co
Failed  Atna Insurance Company
Failed  Aetna Ins. Ca.
Failed  Aetna Insurance Go.
Failed  Aetna Ins. Compary

Matched Sam Jones
Matched Sam J. Jones
Matched Sam J Jones
Matched S. Jones
Failed  Samuel Janes
Failed  Sam L Jones
Matched Sam J.J. Jones
Matched Sam J Jones
Failed  B. Jones
Failed  Manuel Jones
[download]