To see what I've been doing at Hac 07, go to: http://www-users.cs.york.ac.uk/~ndm/temp/haddock/doc-index.html
I have written a searchable index file for haddock, which adds very little file size, and has search-as-you-type features. It doesn't store a separate table of index names. It searches for prefixes only, in O(log n).
There was a version that did full substring searching in O(n), but unfortunately IE is too slow to do this for the base library. If you want that you are still going to have to use Hoogle.
These patches have been bundled up and sent off to Simon Marlow, so hopefully they'll be appearing in a Haddock near you soon!