I have found the solution to my problem in the ZSH documentation. Oh-my-zsh seems to map the ↑ and ↓ Keys to something like
bindkey '\e[A' history-search-backward
bindkey '\e[B' history-search-forward
Which yields the exact behavior I described above. The ZSH Documentation describes the behavior of history-search-backward as
Search backward in the history for a line beginning with the first word in the buffer.
What I wanted instead was the following mapping, which I inserted into my ~/.zshrc:
bindkey '\e[A' history-beginning-search-backward
bindkey '\e[B' history-beginning-search-forward
The behavior of history-beginning-search-backward is as follows:
Search forward in the history for a line beginning with the current line up to the cursor. This leaves the cursor in its original position.
Also, if \e[A doesn't work for the up or down arrows, press <ctrl-v><KEY (e.g., up arrow)> in another terminal which gives ^[OA. Then you can use this instead of \e[A. The process is described here: http://zshwiki.org/home/zle/bindkeys