What about sampling dates and then checking to see if the requested date is available.

use strict;
use Date::Calc qw(Today Add_Delta_YM Month_to_Text);
my @today=Today();

my $months_back;
my @fetchDates;
while ( @fetchDates < 2 ) {
    my @calcDate = Add_Delta_YM(@today[0,1],1,0,$months_back);
    my $date_str = $calcDate[0] .'-'. Month_to_Text($calcDate[1]);
    if ( &dateAvailable($date_str) ) {
        push @fetchDates, $date_str
    }
    $months_back--;
}

print "Retrieving dates:\n".join("\n",@fetchDates)."\n";

sub dateAvailable {
    my $date = shift;
    # check site of date can be downloaded
    return int(rand(2));
}
[download]

I used rand just to show how it would work

2011-February
2011-January

2011-February
2010-December

2010-December
2010-September