How to enable reverse search in zsh?

If I recall correctly, you need to explicitly set it, even with bindkey -v. Use something like this:

bindkey -v
bindkey '^R' history-incremental-search-backward

OMZ framework has zsh-history-substring-search plugin pre-packaged. Just enable & use.

plugins=(git history-substring-search)