bobf: My solution turned out almost identical to yours. However, you will notice that matches and substitutions are done all at once, rather than one at a time. Benchmarked for a million iterations, I got 19 seconds vs 22 for yours.

$_ = 'This is "the search" string "that was" supplied';
my @quotes = (m/"(.*?)"/g); s/".*?"//g;
my @keys = split();
[download]

bart: Benchmarked for the same million iterations, your solution takes 35 seconds. EDIT: Benchmarking methodology is shown below:

use strict;
use warnings;

my $time = time();
for (1..1000000) {
    $_ = 'This is "the search" string "that was" supplied';
    my @quotes = (m/"(.*?)"/g); s/".*?"//g;
    my @keys = split();
} 
print time() - $time;
[download]

Only the mechanical portions of each algorithm were tested. The results can be easily duplicated with cut and paste.