Problem polega na tym, że MySQL nie może w ogóle poprawnie wykonywać REGEX w połączeniu ze znakami Unicode. REGEX zawsze działa na podstawie bajtów, a Unicode musi grupować kilka bajtów. Nie ma rozwiązania, są tylko obejścia.
Jednym z obejść, które zastosowałem, było indeksowanie wszystkich wystąpień liter w innej tabeli, a następnie sprawdzanie indeksu zamiast oryginalnego tekstu japońskiego.