The problem is that, while the plugin's files are deleted, its options are not. These options are stored in the wp_options
table in your database.
Some plugins include an uninstall hook that will clean up the plugins options when removed through the WordPress admin. Not all plugins have this feature, however. You can also look on the plugin's settings page for a 'complete uninstall' option.
I've had much success using the Clean Options plugin. It scans the plugin directory for plugins who are making calls to options in the wp_options
table, and gives you an interface for deleting those that are not referenced. You can ignore the "This plugin hasn't been updated in over 2 years" notice; it works fine with the latest version of WordPress.
You can also try exporting your content through the Tools menu, emptying the database, and importing your content back into the fresh version of WordPress. This will remove all plugin and theme options; you have been warned!