Blev färdig med frågan när svaret slog mig, så postar ändå för kunskapsdelning!
Jag insåg att returvärdet för metafonfunktionen var UTF8.
Jämförelsen med ett latin1-fält medförde uppenbarligen en ganska tung prestanda.
Jag ersatte variabeltilldelningen med:
SET @metaphone_val:= CONVERT(double_metaphone(p_parameter) USING latin1);
Nu går frågan så snabbt som jag förväntade mig.