I believe C-s and C-r in the minibuffer should not only search the
history but the completion table as well (at least when it's not
a function).
There is one problem: what to search first - the history or the
completion table. Either preference will cause inconveniences.
If the user wants to search the history (like implemented in shells),
we should not let isearch to go thru all completion matches before
starting to search the history, and vice versa.
But really there is no need to mix two separate search spaces.
There exist already a convenient key sequence to search the completion
table: `PgUp C-s'. PgUp switches to the *Completions* buffer and
C-s starts searching among completion candidates.