My first plugin to have an uninstaller is WP-Polls and it is contributed by Philippe Corbes. Recently there is a thread [1] in WordPress Forums asking plugin authors to provide uninstaller for their plugins. And that motivated me to add uninstaller to all my plugins, and they will be included in the next release.
I urge all plugin authors to do the same thing to prevent the options table from being overloaded with plugins’ options, and the wost part being that the plugin has already been deactivated and deleted.