One option is to use DBD::AnyData to access the file with DBI and SQL. The script below works using data from the DATA section of a file, but if you substitute in the name of a file containging similar data, it will work just as well.

#!perl -w
use strict;
use DBI;
my @cols  = qw( Name Phone Fax Address Email Info );
my @table = (\@cols);
for my $record(split /\s*%%%\n*/,join '',<DATA>) {
    my @new_rec;
    my @fields = split /\n/, $record;
    for my $field(@fields) {
        $field =~ s/^.*:\s*//;
        push @new_rec, $field;
    }
    push @table, \@new_rec;
}
my $dbh  = DBI->connect('dbi:AnyData:');
$dbh->ad_import('t','ARRAY',\@table);
my $sth = $dbh->prepare("
    SELECT name,email FROM t WHERE address LIKE '%Anywhere%'
");
$sth->execute;
print $sth->dump_results;
__DATA__
Name: Robert Johnson
Phone: (555)555-1111
Fax: (555)555-1112
Address: 12345 Anywhere St.
Email: robertjohnson@someisp.com
Info: more info
%%%

Name: Robert Goor
Phone: (555)555-1113
Fax: (555)555-1114
Address: 12345 Somewhere St.
Email: robert@cs.someu.edu
Info: Some more info
%%%
[download]