Eu não tenho certeza se é possível fazer exatamente o que você estava pensando, mas você pode chegar bem perto (perto o suficiente para fazer o trabalho pelo menos).
Primeiro, você provavelmente tem algo como o seguinte em seu .zshrc:
bindkey '^r' history-incremental-search-backward
E um semelhante para pesquisa direta. Você precisa alterá-los de acordo:
bindkey '^R' history-incremental-pattern-search-backward
Agora você pode usar padrões em suas pesquisas de histórico. Nesse caso, digite control-r (para pesquisa inversa) e, em seguida, digite algo como o seguinte (pressione control-r novamente assim que terminar para procurar seu padrão):
Para "scp" OU "olá" em qualquer lugar da string:
?(scp|hello)
Começando com "scp" seguido de "olá" em qualquer lugar da string:
scp*?(hello)
Nem todo padrão que você pode usar para globbing funciona (por alguma razão, não funciona se você tentar fazer uma busca "AND" estrita com duas expressões onde qualquer um pode vir primeiro), mas isso deve estar perto o suficiente o que você quer.
Boa pergunta, a propósito.