Remove .htaccess portion upon plugin deactivation?

How do you add your rewrite rule?

If you are adding it manually (opening the .htaccess and adding the lines by yourself in php) then you are also supposed to remove it manually. As you suggested the best way would then be to use regex.

If the rewrite rule was added through the WordPress API using add_rewrite_rule() you are able to remove it using flush_rewrite_rules(). You could use it like this:

register_activation_hook( __FILE__, 'myplugin_activate' );

function myplugin_deactivate() {
   global $wp_rewrite;
   unset($wp_rewrite->non_wp_rules['the-string-you-passed-as-param-to-add-rewrite-rule']);
   flush_rewrite_rules();
}
register_deactivation_hook( __FILE__, 'myplugin_deactivate' );