Note that you're discussing to different search methodologies here:
Searching “the vi way” with / or ? will search entire commands stored in history.
What you want the up and down arrow keys to do is something different: You want them to iterate through items stored in history that match (at their start) what you've already typed at the command line.
Without going into too much detail, the following should be a fairly foolproof way of achieving this:
autoload -Uz history-search-end
zle -N history-beginning-search-backward-end history-search-end
zle -N history-beginning-search-forward-end history-search-end
bindkey -M vicmd '^[[A' history-beginning-search-backward-end \
'^[OA' history-beginning-search-backward-end \
'^[[B' history-beginning-search-forward-end \
'^[OB' history-beginning-search-forward-end
bindkey -M viins '^[[A' history-beginning-search-backward-end \
'^[OA' history-beginning-search-backward-end \
'^[[B' history-beginning-search-forward-end \
'^[OB' history-beginning-search-forward-end