The oh-my-zsh project is a fantastic zsh addon, but when vi-mode is activated, the default behaviour doesn’t have a ctrl+r reverse search.
Add the following line to your .zshrc:
bindkey "^R" history-incremental-search-backward
And then reload your zsh, the backward search is there.
thanks!