一旦、連想配列にデータをぶちこんで、それで直接アクセスするやり方。
キーをタブ結合(タブじゃなくてもいいけど)で、一つにするのがポイント。
┌──────────────────────────────────────┐
│Dim yMax As Long, y As Long, 連想配列 As Object, キー As String             │
│Set 連想配列 = CreateObject("Scripting.Dictionary")                         │
├──────────────────────────────────────┤
│' 連想配列に格納                                                            │
│With 参照シート                                                             │
│    yMax = .UsedRange.Rows(.UsedRange.Rows.Count).Row                       │
│    For y = 2 To yMax                                                       │
│        キー = .Cells(y, Xキー1).Value & vbTab & .Cells(y, Xキー2).Value    │
│        If Not 連想配列.Exists(キー) Then                                   │
│            連想配列.Add キー, .Cells(y, Xバリュー).Value                   │
│        End If                                                              │
│    Next y                                                                  │
│End With                                                                    │
├──────────────────────────────────────┤
│' 連想配列を検索                                                            │
│キー = キー1 & vbTab & キー2                                                │
│If 連想配列.Exists(キー) Then                                               │
│    MsgBox 連想配列(キー)                                                   │
│End If                                                                      │
└──────────────────────────────────────┘
結構速いし、小難しい処理(該当なしで例外とか)がないのでいいかも。