I think the history substring search does exactly what you want; I have setup the following keybindings
bindkey '^[[A' up-line-or-search
bindkey '^[[B' down-line-or-search
bindkey '^P' up-line-or-search
bindkey '^N' down-line-or-search
That way I start typing any part of a previous command, press the up-arrow or Ctrl-P and get commands matching that written part anywhere from my history in reverse order - as you described.
Edit: And of course, if you don't want to install the history-search plugin, C-r
does also match complete command lines in your history.