How to make ctrl+p behave exactly like up arrow in zsh

You've probably got INC_APPEND_HISTORY set.

The INC_APPEND_HISTORY option, from man zshoptions:

This options works like APPEND_HISTORY except that new history lines are added to the $HISTFILE incrementally (as soon as they are entered), rather than waiting until the shell exits.

The option that you want is APPEND_HISTORY:

APPEND_HISTORY If this is set, zsh sessions will append their history list to the history file, rather than replace it. Thus, multiple parallel zsh sessions will all have the new entries from their history lists added to the history file, in the order that they exit. The file will still be periodically re-written to trim it when the number of lines grows 20% beyond the value specified by $SAVEHIST (see also the HIST SAVE BY COPY option).

You can read about these options in the man zshoptions, man zshall or online here.

To set them, in your ~/.zshrc or similar, you should have:

setopt APPEND_HISTORY

Be aware that, if you're using oh-my-zsh by default, I believe, INC_APPEND_HISTORY is used. I'm not 100% sure which way around things get loaded, but if the oh-my-zsh option overrides the one you've set in ~/.zshrc, you can fiddle with it in ~/.oh-my-zsh/lib/history.zsh

The behaviour described is due to the use of up-line-or-search, which will move up through the line of a command and on the first line of a command it will search in the history for lines beginning with the first word.

Explanation for your issue: Starting from an empty line any line in the history will match. As long as only single-line commands are found there is no difference in behaviour to up-history or up-line-or-history. But when reaching a multi-line command it is no longer searching but going through the lines. When the top line is reached it starts a new search, but now it is looking for the first word in this line instead of continuing the old search for any line.

By default Up is mapped to up-line-or-history, which goes backward through the history entries and in case of multi-line commands through each line. up-history would also go through the history but treat multi-line commands just like single-line ones. Both would provide the expected behaviour.

I'd suggest searching your zsh and Oh-my-ZSH configuration for where up-line-or-search is bound and replace it with up-line-or-history or delete the binding as up-line-or-history is the default anyway.

Also, depending on the terminal used, the key sequenze for Up is either ^[OA or ^[[A. To get consisten behaviour from your shell, both should be set to the same commands.