jemswira,
Is there anything faster than checking like this?

Yes. Or rather, maybe. It is hard to tell from your pseudo notation if you have a hash of arrays, a hash of hashes or just a hash with weird key/value pairs. Assuming you have a hash of hashes then yes.

my @tocheck = qw/Apple Corn Pie Fish/;
my %checkfrom = (
    Meat => {
        Fish => 1,
        Apple => 1,
        Pork => 1,
        Bacon => 1,
    },
    Fruit => {
        Apple => 1,
        Pie => 1,
        Orange => 1,
        Beef => 1,
    },
);
for my $thing (@tocheck) {
    for my $category (keys %checkfrom) {
        delete $checkfrom{$category}{$thing};
    }
}
[download]

If your pseudo notation implied something else. Use real code and repost.