There are different approaches to this, depending on specific requirements.
For example in your case you seem more worried about plugin picking up ghost data than that data being left behind. Such case might be easier handled by generating unique key prefix to use and just flushing that on uninstall. No prefix = no data access.
I would say the general case is to ignore the issue and to use appropriate timeout values for transients. If data is only relevant for specific amount of time then using appropriate timeout handles it implicitly just fine.
Options can (should) be stored as single set, so clearing those out is easy and fast.