Your database might be fragmented or there is an issue with it then. The plugin does not take up the space, it only instructs the database to store the information. Once the information is deleted, the space should be freed up. Make sure to also check if you have any automatic backup system active – because that will still store an archive of the tables for days or even weeks.
Try running optimize table and mysql query cache clear commands.
You can also try the plugin wipe – it will delete all the database tables as well, that should trigger the database server to clear all the cache or any leftover junk. Then if you reactivate the plugin, it will start from fresh.