Sin duplicados, 2 condic, sin ordenar y blancos

Se me ocurren dos posibilidades.
La más fácil sería crear en una columna aparte la unión de los 2 valores anteriore (=B2 & O2). Hecho eso sería más fácil saber si un valor ha aparecido antes usando la función buscarv.
La otra solución es definirte una función dentro de un módulo VB. El código sería este:
Option Explicit
Function contarvaloresunicosBO(ByVal rangoB As Range, ByVal rangoO As Range) As Long
    Dim anteriores As String ' Para construir una lista de valores ya vistos
    Dim i As Long
    Dim n As Long
    Dim aux As String
    Dim c0 As String ' Para no llamar todo el rato a la funcion chr$(0)
    contarvaloresunicosBO = -1    ' Valor ilógico para caso de error
    ' Chequeamos los datos de entrada
    If rangoB.Columns.Count > 1 Then
        MsgBox "El rango B no puede tener más de una columna"
        Exit Function
    End If
    If rangoO.Columns.Count > 1 Then
        MsgBox "El rango O no puede tener más de una columna"
        Exit Function
    End If
    If rangoB.Rows.Count <> rangoO.Rows.Count Then
        MsgBox "Los dos rangos deben tener el mismo número de filas"
        Exit Function
    End If
    n = 0
    ' Usaremos el carácter 0 como separador porque no se puede poner
' en la página de datos.
    c0 = Chr$(0)
    anteriores = c0 & c0
    For i = 1 To rangoB.Rows.Count
        ' Si alguna de las celdas tiene algo, hacemos el proceso.
        ' Si las dos están en blanco las saltaríamos
        If rangoB.Cells(i, 1) <> "" Or rangoO.Cells(i, 1) <> "" Then
            ' Guardamos en una variable auxiliar el valor de los dos
            ' Campos unidos y separados por el carácter 0
            aux = rangoB.Cells(i, 1) & c0 & rangoO.Cells(i, 1)
            ' Si ese valor, con dos caracteres 0 delante y otros tantos detrás no
            ' Está en nuestra lista... es nuevo. Lo contamos y añadimos a la lista
            If InStr(anteriores, c0 & c0 & aux & c0 & c0) = 0 Then
                n = n + 1
                anteriores = anteriores & aux & c0 & c0
            End If
        End If
    Next i
    ' Los valores únicos serán los que hemos contado en "n"
    contarvaloresunicosBO = n
End Function
Después sólo tienes que poner en una celda la fórmula:
=contarvaloresunicosBO(Hoja2!B12:B65000;Hoja2!O12:O65000)
La función utiliza el carácter ASCII 0 para separar el contenido de las dos celdas y en la lista de valores anteriores, porque es un carácter que no se puede teclear en Excel y por tanto no puedes escribirlo en tus celdas.

El código no lo entiendo bien. Lo he copiado y me da -1, imagino que será por el chr(0) que no se donde ponerlo; lo de unir las dos celdas en una magnífica idea, pero lo he probado poniendo otra columna, la P, con
=N(SI(O13="aaa";B13+10000; (SI(O13="bbb";B13+100000;(SI(O13="ccc";B13+1000000)))))) en cada hoja del libro
y después en hoja aparte
=CONTAR(SI(FRECUENCIA(Hoja2!P12:P65000;Hoja2!P12:P65000)>0;1))
Y no me hace bien la frecuencia.
Gracias por contestar