Na verdade a lógica fuzzy não retorna percentual de igualdade, mas um grau de similaridade entre valores. Mas isso é só conceito, rs.
Bom, vamos lá, o SOUNDEX não sei se é uma boa pois ele é mais para fonética, se tiver diferença na string, como por exemplo um “de” a mais (como no seu exemplo), eu acho que ele não pegaria. Talvez você tenha que trabalhar com o CONTAINS e índices CONTEXT, ordenando seu resultado pelo SCORE. Mas fique ciente de que isso vai acrescentar bastante overhead de processamento na tua consulta.