I'd recommend a refinement of your second technique-- use a single if statement, but break up your conditions into small subroutines with descriptive names.

if ( date_in_range     ( $today, $start, $stop ) &&
     date_not_bad      ( $today, @notthisday   ) &&
     good_day_of_month ( $day, @dayofmon       )
{
    print "$today is the day";
}

sub date_in_range {
    my ( $today, $start, $stop ) = @_;
    return $today > $start && $today < $stop;
}
sub date_not_bad {
    my ( $today, @notthisday ) = @_;
    return $today != $notthisday[0] &&
           $today != $notthisday[1] &&
           $today != $notthisday[2]; 
}
sub good_day_of_month ( $day, @dayofmon ) {
    my ( $day, @dayofmon ) = @_;
    return $day == $dayofmon[0] ||
           $day == $dayofmon[1];
}
[download]

Untested code, but that gets the idea across.

Chapters 12 and 14 of Code Complete also talk about various fun methods of optimizing if blocks.