Terminei de escrever a pergunta quando a resposta me atingiu, então postando de qualquer maneira para compartilhamento de conhecimento!
Percebi que o valor de retorno da função metafone era UTF8.
A comparação com um campo latino1 estava obviamente incorrendo em uma sobrecarga de desempenho bastante pesada.
Substituí a atribuição de variável por:
SET @metaphone_val:= CONVERT(double_metaphone(p_parameter) USING latin1);
Agora, a consulta é executada tão rápido quanto eu esperaria.
