what if when you'r deliting plugin there would be an alert ( just like now, when u press delete perminantly ) may be after that could come anothere alert with question:
do you want to keep plugins data or delete it from database.
If person selects delete than you could search throught all plugin files ( .php ) and look for
add_option(), update_option() CREATE TABLE atc. key words for keeping plugins data..
( i hope the idea is clear ).
and after you got all the 'keys' of add_option() you could do delete_option('keys');
aldought idea might be good - there's a problem if plugin is using 100+ files and more.. to read each file would lead to something bad.
as well as deliting something important ( like core 'keys' if plugin is updating )..
Anothere way could be:
before plugin is activated to make a copy of db and one copy after plugin is activated ( and created his options ).
Compare these 2 fields and write in db new option keys that plugin has added..
when uninstalling - delete these options..
(could be count( wp_options rows ) before activated and after activated ). for ex. if plugin added 2 options the difference betwine 2 counts will be 2.. so latest added 2 rows in wp_options is from new plugin.. remember them and delete when uninstalling