Eu usaria o suplemento de pesquisa difusa para isso. Ele será lido em duas tabelas e retornará a melhor correspondência (ou correspondência), juntamente com as pontuações de confiança e similaridade.
Eu não posso seguir seu segundo parágrafo acima, mas acho que para o seu cenário eu executaria uma primeira passagem usando o primeiro par de colunas. Então eu criaria uma nova planilha com apenas as linhas + linhas sem correspondência com baixa pontuação de confiança e similaridade. Em seguida, eu executaria uma segunda pesquisa difusa usando o segundo par de colunas. A última tarefa seria coletar todos os jogos juntos.
Se esta for uma tarefa única, eu apenas faria essas etapas manualmente. Se precisar ser repetido, eu o colocaria em Consultas usando o Power Query Add-In, para automatizar a divisão e o agrupamento de dados. Você não pode automatizar a chamada do Fuzzy Lookup Add-In (ainda - ouvi dizer que eles estão trabalhando nisso), mas você pode automatizar as outras etapas.