This package enables incremental-searching on minibuffer history.

Put this code into your .emacs:

(require 'minibuf-isearch)

Then type C-r in minibuffer and you'll be happy.  (yes, I suppose!)
See 'M-x describe-function minibuf-isearch-mode' for details.