Seu problema não está no formato, está no valor real. As datas são armazenadas como números de ponto flutuante, em unidades de dias. Alterar o formato não altera a forma como a data é armazenada ou como o vlookup corresponde a ela. Nesta imagem, a terceira coluna mostra o valor que o Excel tem em mente quando mostra o valor na segunda coluna.
Você precisa recuperar apenas a parte do dia, então use rounddown(YourDate,0)
Isso pode acontecer dentro da sua fórmula de vlookup, é claro. Por exemplo, se a tabela de pesquisa estiver em c2: d367 e a data em que você estiver procurando estiver em A1:
vlookup(rounddown(A1,0), $c$2:$d$367,2)