No, deactivating is not enough. A well coded plugin will normally delete its options/files when it is uninstalled.
Others, as an extra feature may offer this clean-up in its own page, but that’s not common.
So, you’ll need to deactivate, delete and install again.
This can be short-circuited inspecting the plugin’s register_uninstall_hook or uninstall.php file, and executing the needed actions by your own.
In BackWPUp case, it’s done via file, not hook. And in uninstall.php we can see that the following MySQL query is needed:
"DELETE FROM " . $wpdb->options . " WHERE option_name LIKE '%backwpup_%' "
$wpdb->options corresponds to your wp_prefix_options table. This is for a normal WP install, if you’re running a Multisite, the table is $wpdb->sitemeta.
To test it out, run first in PHPMyAdmin:
SELECT * FROM wp_options WHERE option_name LIKE '%backwpup_%'
and then proceed to:
DELETE FROM wp_options WHERE option_name LIKE '%backwpup_%'