Existem duas seqüências de escape padrão para chaves de cursor; terminais diferentes, ou até mesmo o mesmo terminal em modos diferentes, podem enviar um ou outro. Por exemplo, xterm envia \eOA para Up em “modo de cursor de aplicativo” e \e[A caso contrário. Para Down você pode encontrar tanto \e[B como \eOB , etc.
Uma solução é duplicar suas ligações: sempre que você ligar uma sequência de escape, ligue a outra seqüência de escape ao mesmo comando.
bindkey '\eOA' history-beginning-search-backward
bindkey '\e[A' history-beginning-search-backward
bindkey '\eOB' history-beginning-search-forward
bindkey '\e[B' history-beginning-search-forward
Outra abordagem é sempre ligar uma sequência de escape, e fazer a outra seqüência de escape injetar a outra.
bindkey '\e[A' history-beginning-search-backward
bindkey '\e[B' history-beginning-search-forward
bindkey -s '\eOA' '\e[A'
bindkey -s '\eOB' '\e[B'
Eu não sei porque a atualização do oh-my-zsh teria afetado a seqüência de escape que o shell recebe do terminal. Talvez a nova versão realize uma inicialização de terminal diferente que habilite o modo de cursor do aplicativo.