Parece que o problema é que a MATCH só funciona com células com um máximo de 255 caracteres. Assim que o comprimento for além disso, ele retornará um erro. Para contornar isso, usei a seguinte fórmula:
=INDEX(A:A;MATCH("*"&F1&"*";MID(B:B;SEARCH(F1;B:B);20);0))
Como é uma fórmula de matriz, ela precisa ser confirmada com CTRL + SHIFT + ENTER . Isso funciona também se a string que você procura estiver além do 255º caractere.
Um grande obrigado @jonno que me apontou na direção certa!