I guess I will throw mine in as well...
Caveat, your response list will have 0 padded months, but that would be easy enough to correct.... Matter of fact I will, just give me a minute... :)
UpdateRemoved 0 padding in response list.

use strict;
use Data::Dumper;

my @temp = ( [ qw( testthis 2000-4 2000-2 2000-1 2000-12 2001-1 2002-1
+2 1999-12 ) ], # bad
             [ qw( testthis 1999-1 1999-2 1999-3 1999-4 1999-5 1999-6 
+1999-7 1999-8 1999-9 1999-10 1999-11 1999-12 2001-3 ) ], # bad
             [ qw( 1999-1 1999-2 1999-3 1999-4 1999-5 1999-6 1999-7 19
+99-8 1999-9 1999-10 1999-11 1999-12 2000-1 ) ], # good
             [ qw( 1998-12 1999-1 ) ], # good
             [ qw( 2004-1 ) ], # good
             [ qw( 2004-12 ) ], # good
             [ qw( 2004-12 2004-11 ) ], # good
             [ qw( testthis 2004-12 2004-9 2004-11 ) ] ); # bad
foreach ( @temp ) {
    my %dates = map { s/-(\d)$/-0$1/; $_, '' } @$_;
    if ( exists $dates{ 'testthis' } ) {
        delete $dates{ 'testthis' };
        print Dumper( \%dates );
        my ( $missing ) = find_gaps( \%dates );
        print Dumper( $missing ), '-' x 20 ,"\n";
    }
}


sub find_gaps {
                my $dates = shift;
            my @date_list = sort keys %$dates;

                my $c_date = shift @date_list;
                inc_date(\$c_date);
                my @gaps = map { trap_gap(\$c_date, $_); } @date_list;
                                s/-0(\d)$/-$1/ for @gaps;
                return \@gaps;
}

sub inc_date {
                my $date = shift;
                my ($y, $d) = split('-', $$date);

                if ($d == 12) {
                                    $y++; $d = 01;
                } else {
                                $d++;
                }

                $d = "0$d" if $d < 10;

                $$date =  "${y}-${d}";
}

sub trap_gap {
                my ($c, $t) = @_;
                my @res = ();
                if ($$c eq $t) {
                                inc_date($c);
                                return ();
                }
                while ($$c ne $t) {
                                push(@res, $$c);
                                inc_date($c);
                }
                inc_date($c);
                return @res;
}
[download]