I think that roboticus has the ticket with the "uniq" function for question #1. List::MoreUtils is an XS module and should run very fast.

As a thought for question #2, here is some Perl 5.10 code using the smart match operator (~~).

#!/usr/bin/perl -w
use strict;
use 5.10.0;

my @a = qw(alpha beta gamma zulu);
my @b = qw(delta alpha kappa gamma beta);

my @c = grep{!($_ ~~ @a)}@b;
print "@c";    #prints: delta kappa

# @c is @b after removing any element
# that was contained in @a
[download]

This is my first program with this new Perl 5.10 "~~" operator and I have no idea of how "smart" or not "smart" this new operator really is, especially in a loop like above. I would have to run some benchmarks, but since this is one line of code, I leave that to the OP to experiment with and present this as just an idea.