Remove data only on uninstall. Deactivating plugins can be done by mistake or in order to troubleshot some other problem and you don’t want to make the plugin users to config everything again in this situation.
Think about your PC software, does it delete its data when it is being closed and become inactive? no, only when it is uninstalled. Same applies here.
Actually the uninstall option is relatively new and it was created specifically to have a point where you know it is safe to delete data.