Custom Rewrite Rules Not Sticking

I’ve written some custom rewrite rules for a special feature on http://www.pewhispanic.org/states/. States is a page with a custom page template, page-states.php. The logic for returning the right data based on the request is done there.

I created custom rewrite rules so I could have a pretty urls with custom parameters that get sent to page-states.php. The following code is in my themes functions.php file:

//Rewrites for the States and Counties Database
function filter_statedb_rewrite_rules( $wp_rewrite ) { //Lets us have URLs like /states/state/md/ etc.
    $statedb_rewrite_rules = array(
        "states/counties/([a-zA-z]{2})/?$" => "index.php?pagename=states&counties=" . $wp_rewrite->preg_index(1),
        "states/county/(d+)/?$" => "index.php?pagename=states&countyid=" . $wp_rewrite->preg_index(1),
        "states/state/([a-zA-z]{2})/?$" => "index.php?pagename=states&stateid=" . $wp_rewrite->preg_index(1)
    );
    $wp_rewrite->rules = $statedb_rewrite_rules + $wp_rewrite->rules;
}
add_action('generate_rewrite_rules', 'filter_statedb_rewrite_rules');


function kill_statesdb_canonical_redirect($redirect_url, $requested_url) {
    global $wp;

    $statedb_rewrite_rules = array(
        "states/counties/([a-zA-z]{2})/?$",
        "states/county/(d+)/?$",
        "states/state/([a-zA-z]{2})/?$"
    );

    if( in_array($wp->matched_rule, $statedb_rewrite_rules) ) { 
        return false;
    } else {
        return $redirect_url;
    }
}
add_filter('redirect_canonical', 'kill_statesdb_canonical_redirect', 10, 2);


function add_statedb_query_vars($query_vars) {
    $query_vars[] = 'counties';
    $query_vars[] = 'countyid';
    $query_vars[] = 'stateid';

    return $query_vars;
}
add_filter( 'query_vars', 'add_statedb_query_vars' );

For some reason the rewrite rules fail to stick sometimes (I hate when things only work sometimes). I visit Settings -> Permalinks to flush the rewrite rules and everything is working great. A couple days go by and then I get an email saying pages like http://www.pewhispanic.org/states/state/md/ are returning a 404. Crap. I go and flush the rewrite rules and everything is fine again.

What am I missing here? Why are my custom rewrite rules sometimes not being applied? Is there a better action than generate_rewrite_rules to hook on to? Do I even need to mess with the redirect_canonical filter? I don’t think it’s doing anything.

Any insight would be most appreciated.