What about plugins that don't create their own tables, but leave their data behind in wp_options? I've been surprised a few times to see options in there for plugins that had been deleted years prior to me poking around.

Data cleanup upon uninstall should apply to stuff in the main WP tables as well.