Remove rewrite rules generated by plugin during deactivation‎

You’re adding your rewrite rules to $wp_rewrite->rules, but then not removing them before calling the flush during deactivation. Add code to your deactivation function to remove the stuff you added to $wp_rewrite->rules before calling flush_rewrite_rules().