Here's a solution based on a regex. It may run a long time if you have 50 couples celebrating their 50th Christmas though.

#!/usr/bin/perl
    
use strict;
use warnings;
    
my %people = (
    jim    => ['betty',  'claire'],
    betty  => ['frank',  'jim'   ],
    frank  => ['claire', 'john'  ],
    claire => ['john',   'betty' ],
    john   => ['jim',    'frank' ],
    nancy  => ['',       ''      ],             # new girl
);

my @names = keys %people;  
    
my $str = "";
my $re  = "";
    
my $i;
foreach my $name (@names) {
    $str .= "$name:";
    my %not;
    @not {$name, @{$people {$name}}} = ();
    $str .= join "," => grep {!exists $not {$_}} @names;
    $str .= "\n";
    $re  .= ".*\\b";
    $re  .= "(?!\\$_)" for 1 .. $i ++;
    $re  .= "(\\w+)\\b.*\n";
}

if (my @a = $str =~ $re) {
    foreach my $name (@names) {
        printf "$name picks %s\n" => shift @a;
    }
}
else {
    print "No solution possible.\n";
}
__END__
nancy picks frank
john picks betty
claire picks jim
betty picks claire
jim picks john
frank picks nancy
[download]

Abigail

But next year they'll each have three names in their lists. This can take a minute or more!

Abigail

1. and randomly chosen recipient are the same person
2. The giver has given to the recipient before

Unfortunately, the likly hood of completing the task diminishes as the number of people in the list compared to the number of people that they have given to becomes close. The iteration count is added in order to stop an infinite loop if a solution cannot be found. I have decided to terminate the script if a solution is impossible but another loop could be added to keep going until a solution was found.

#! /usr/bin/perl -w

use strict;
use warnings;

my %people = (
    jim    => ['betty',  'claire'],
    betty  => ['frank',  'jim'   ],
    frank  => ['claire', 'john'  ],
    claire => ['john',   'betty' ],
    john   => ['jim',    'frank' ],
    nancy  => ['',       ''      ],             # new girl
);

my @allPeople = sort keys %people;
my %recipients;
@recipients{@allPeople}=undef;

srand; # randomize!
foreach (@allPeople)
{    
    my @remainingPeople = keys %recipients;
    my $randPerson;
    my $iterations;
    do
    {
        $randPerson = $remainingPeople[int (rand ($#remainingPeople))]
+;
        $iterations++;
        die ("ERROR: Failed to generate list\n") unless ($iterations <
+$#allPeople);
    } until (testRecipient($_, $randPerson));
    
    print "$_ can give to $randPerson\n";
    delete $recipients {$randPerson};
}

sub testRecipient
{
    my ($santa, $recipient) = @_;
    my $arrayref = $people{$santa};

    # test for self giving
    return 0 if ($santa eq $recipient);
    
    #test for giving to the given
    foreach (@$arrayref){
        return 0 if ($_ eq $recipient);
    }
    return 1;
}
[download]

Comments on the code (especially dereferncing the anonymous array reference contained in the hash element) is most welcome!

Suppose there were a constant group of 5 friends. The following block would set up a schedule for four years, such that each gives to each of the others without repeats.

1 2 3 4 5
5 1 2 3 4
4 5 1 2 3
3 4 5 1 2
2 3 4 5 1

You would read down the columns, so that the first year person 1 gives to person 5, and the next year to person 4, and so on. You could most likely fit in old information into the pattern by appropriate assignment of numbers and rearrangements of rows.

All you need is a latin square of appropriate size to plan for any number of people.

Yeah this is all very very easy:

my @names = qw/andy betty craig daniel edith/;
my %reverse_lookup;
@reverse_lookup{ @names } = (0..4);

foreach $year (2004 .. 2007) {
    foreach (sort keys %people) {
        printf("%04d: %s buys for %s\n", 
            $year, 
            $_, 
            $names[ ($year+$reverse_lookup{$_}) % 4 + 1]
        );
    }
}
[download]

However, the group isn't constant. My original data introduces nancy after two years, if we suddenly do this then a latin square doesn't work.

Also, I must point out that there will be data such as sally can never buy for derek ... not after last years christmas party. So derek is on sally's list .. permanently. Even after we reset it at the end of the cycle.

I saw the addition of Nancy after two years in your original data, but I chose to ignore it because it makes a full solution impossible. Suppose we wanted to continue the pattern for the next four years. Andy, Betty, Craig, Daniel, and Edith each want to buy something for Nancy (and for the other three they have not bought for yet) before they go back to anyone earlier on their list. That's five buyers for Nancy in four years, which won't work.

I think the best you can do when a new person is added is to compute a new latin square from that point and try to place the previous pairings as low in the square as you can.

I also think I could prove that having one person who cannot buy for another also makes a full cycle impossible. In that case, you could place that pairing on the last line of the latin square, and start a new square when you get to that point.