I've also asked the question here: http://drupal.org/node/250783#comment-7059582
I've been testing this with my own module, to make sure that all information is removed from the database for the module when it's uninstalled.
I've also compared it with another module and have some points:
1) it seems that all modules appear in the uninstall list, even if it doesn't have an uninstall feature (in the .install file or this file is missing).
2) The modules I've looked at (even mine) creates permissions. These are not removed from the database (role_permission) when it's uninstalled but don't work correctly (or show correctly) when the module is enabled again.
There must be somewhere else in the database that holds these permissions because this table hasn't changed.
Can someone shed some light on this? I will also report this elsewhere to try and get an answer.