One of the most annoying task in WordPress is to keep the wp_option table as clean as possible.
I think that if all WP functions that stores data in this table would also add information about who uses a specific option (see below for details) would help keeping clean the table.
I'm thinking to some king of 1-n relationship (or a text field containing serialized data), as option might be used by one or more themes/plugins.
Each time a function that reads from wp_option gets called, it must know who's is calling it (either by simply finding function caller, or requesting a specific parameter).
Of course, the same applies when a function that writes option is called.
When a theme or plugin is (properly) deleted, WP could take care of cleaning these options (as long as they aren't used by something else).