Hoppla, ich habe also die Antwort auf mein Problem gefunden:
Alle Spalten eines FULLTEXT-Indexes müssen nicht nur den gleichen Zeichensatz, sondern auch die gleiche Sortierung haben .
Mein FULLTEXT-Index hatte utf8_unicode_ci in einer seiner Spalten und utf8_general_ci in seinen anderen Spalten.