Ok, I'm trying to implement a finder based on configured paths (PYTHON_HOME, PYTHON_HOME/site-packages, PYTHON_PATH), maybe looking up 'pth' files as well. This will be an approximate search (not sure of the details yet) and will not use any kind of introspection. Maybe the PYTHON_HOME could be asked for the first time the dialog is opened.
In the meantime I'm temporarily adding a checkbox to the dialog so I can use the simple __import__-based algorithm (I have installed the plugin and I'm using it).
About the index: in my opinion that should be a tool in itself, that is, a general purpose index, a service other pytools modules could use, for example the completer. I mean, if you take the effort of managing an index (creating it, updating it, etc), maybe it is worth to store into it something more than the modules definitions and path.