WP core should provide a hook for plugins to execute when the user wants to delete the plugin.
The plugin administration panel should as well provide a button to delete a plugin's folder and a checkbox that would indicate if the user want to delete all the plugin data from database or just the files.
This would allow plugin developpers to have a standard procedure to delete the plugin tables, options, remove extra columns, ...