Date based redirects of posts that no longer exist

It is no problem that the posts are already gone, we will hook into WP before it queries the database. First we set up our rewrite rules, which will set a special query variable (that we must declare public), and then, in the parse_request action, we check for that variable and redirect if it is set.

add_action( 'init', 'wpse8236_init' );
function wpse8236_init()
{
    // This is case-sensitive, we can't set regex flags
    // Replace `blog` with `[Bb][Ll][Oo][Gg]` to make it case-insensitive
    add_rewrite_rule( 'blog/2008/', 'index.php?wpse8236_redirect=true', 'top' );
    add_rewrite_rule( 'blog/2009/0[1-6]/', 'index.php?wpse8236_redirect=true', 'top' );
}

add_action( 'query_vars', 'wpse8236_query_vars' );
function wpse8236_query_vars( $query_vars )
{
    $query_vars[] = 'wpse8236_redirect';
    return $query_vars;
}

add_action( 'parse_request', 'wpse8236_parse_request' );
function wpse8236_parse_request( &$wp )
{
    if ( array_key_exists( 'wpse8236_redirect', $wp->query_vars ) ) {
        wp_redirect( '/blog/' );
        exit();
    }