Rather than modifying stored rules it would be more reliable to modify rules before they are stored.
flush_rewrite_rules()
callsWP_Rewrite->flush_rules()
WP_Rewrite->wp_rewrite_rules()
WP_Rewrite->rewrite_rules()
Inside last there are fitting hooks to modify rules (after which result they will be saved as usual on each flush):
do_action_ref_array('generate_rewrite_rules', array(&$this));
$this->rules = apply_filters('rewrite_rules_array', $this->rules);