Você deve conseguir fazer isso com uma fórmula como esta:
=IF(ISNA(MATCH(A1,Sheet2!$A$1:$A$150000,0)+MATCH(B1,Sheet2!$B$1:$B$150000,0)+MATCH(C1,Sheet2!$C$1:$C$150000,0)),"No Match","Match")
Se não encontrar um deles, você recebe "No Match". Se encontrar todos os três, você recebe "Match".
Editar: se você estiver verificando se todos estão na mesma linha, use algo assim:
=IF(ISNA(MATCH(A1&B1&C1,Sheet2!$A$1:$A$150000&Sheet2!$B$1:$B$150000&Sheet2!$C$1:$C$150000,0)),"No Match","Match")
Esta é uma fórmula de matriz, por isso, precisa ser digitada usando Ctrl + Shift + Enter.