Приключих с писането на въпроса, когато отговорът ме удари, така че все пак публикувам за споделяне на знания!
Разбрах, че върнатата стойност на функцията за метафон е UTF8.
Сравнението с поле latin1 очевидно доведе до доста тежко изпълнение.
Замених присвояването на променлива с:
SET @metaphone_val:= CONVERT(double_metaphone(p_parameter) USING latin1);
Сега заявката работи толкова бързо, колкото очаквах.