Você tinha up-line-or-search
ligado à sua seta para cima. Isso deve fazer o que você quer:
bindkey '^[[A' up-line-or-search
bindkey '^[[B' down-line-or-search
[Editar]:
O comando acima usa apenas a primeira palavra para pesquisar. O seguinte irá usar toda a linha. Veja man zshcontrib
...
autoload -U up-line-or-beginning-search
autoload -U down-line-or-beginning-search
zle -N up-line-or-beginning-search
zle -N down-line-or-beginning-search
bindkey "^[[A" up-line-or-beginning-search # Up
bindkey "^[[B" down-line-or-beginning-search # Down