Existem várias maneiras de se fazer isso. Uma delas é criando uma coluna temporária em que você concatena as informações que você quer pesquisar e bastaria usar o PROCV() pesquisando com base nos campos concatenados.
Por exemplo, supondo que cidade está na célula B1, você concatenaria as informações correspondentes a cidade, rua e número, assim:
=B2&"-"&C2&"-"&D2
Esta fórmula, por exemplo, estaria na célula "A2" e seria repetida para as linhas de baixo.
Então você poderia usar o PROCV() usando como valor procurado a concatenação dos campos. Exemplo:
=PROCV("Santos"&"-"&"Pátria"&"-"&"22";$A$2:$C$10;5;0)
Nota 1: Não precisa colocar o "-", mas eu adiciono para ver melhor o resultado produzido (às vezes, se houver um campo vazio pode não encontrar se não colocar um delimitador).
Nota 2: Quando for fazer de fato, você vai substituir o "Santos"&"-"&"Pátria"&"-"&"22" pela concatenação dos campos (células) que estiver pesquisando, imaginando que o usuário vai preencher estas três informações em outras células.
Nota 3: Você pode ocultar a coluna temporária (no caso, a coluna A). Ou poderia usar o índice() com corresp() se quiser deixar em uma coluna mais à direita da planilha.