Taxonomy “data” is indeed stored in the database. Taxonomy “definitions” are not.
The stuff you put into a call to register_taxonomy is not the data, it’s the definition of that data. Stuff you add, like categories or tags, is the data, and yes, it goes in the taxonomy tables like any other taxonomy data.
You need to call register_taxonomy every time so that WordPress knows the taxonomy exists and how to deal with it. The data from the taxonomy comes from the database. Your definition of the taxonomy comes from the code.
Additional:
The question of how you should delete data entered by the user actually is more complex than just the technical means. All the means you mention work, but the real question is whether or not you should delete that data. Maybe the user put a lot of hard work into defining those geoareas themselves. If they remove and reinstall your plugin and the data is now just vanished forever, then that’s kind of a terrible thing.
Also, you absolutely should not remove such data on register_deactivation_hook, because people can deactivative and reactivate a plugin easily. If you were going to remove data, it would be on an uninstall.php file in the plugin (which, unsurprisingly, only runs on an actual uninstall of the plugin, and not mere deactivation). A better approach might simply be to provide the user with a “wipe all the data” button instead. Put control of their data into their own hands.
If the data in question is unchanging and created automatically somehow, then regenerating it after a fresh install might make sense, but that’s pretty rarely the case for taxonomies. Might want to reconsider your overall strategy instead.