Con fórmulas lo podrías hacer apoyándote en columnas auxiliares. Sería una especie de comprobación dinámica.
El primer paso es crear una tercera columna en la pestaña de las fórmulas. Concatenas el valor de clave1 y clave2, será una clave "maestra" unión de ambas:
=A2&B2
Ahora en la otra pestaña creas otra columna cuya misión es comprobar si existe en la pestaña anterior una combinación del valor de columna1 y columna2. Te comento dos formas:
-La más simple es con un contar.si() de tal forma que si su valor es uno o más es una combinación de claves válidas y si es cero no es valida:
=CONTAR.SI(Hoja1!C:C;Hoja2!A2&Hoja2!B2)
Nota: hoja1 la pestaña dónde están las claves
Señalar que si arrastras la fórmula donde no hay valores saldrá un valor muy alto igual al número de filas en blanco de la hoja.
Una ventaja del contar.si() es el hecho de permitirte verificar si tienes alguna dupla de clave1 y clave2 duplicada.
-Otra solución más elegante es añadir un par de si() anidados. Utilizaremos un si() para contemplar el caso de celdas donde no hay valores y otro si() para mostrar un mensaje confirmando la corrección de las claves o avisando que son incorrectas:
=SI(A2&B2="";"";SI(CONTAR.SI(Hoja1!C:C;Hoja2!A2&Hoja2!B2)>0;"Claves OK";"Claves incorrectas"))
Si no tenemos problemas en trabajar con una celda más o que esté oculta, la concatenación de A2&B2 en la segunda hoja puede ser hecha en otra columna y desde la columna con los si() y el contar.si() apuntar a esta nueva columna auxiliar. Ganaremos en legibilidad y tener una mejor base para explotar la hoja1.