Does your relative search do 16 bit encoding searches? Or possibly can you insert a wildcard between the values to mimic it? I don't tend to use windhex for relative search so don't know its limitations and general workflow here. Monkey moore is my chosen toy for this sort of thing https://www.romhacking.net/utilities/513/
Anyway you can't fit all the Japanese characters into 8 bit encoding (at least not without cycling it out which is tedious and quite limiting) so most things opt to use 16 bit encodings which can make life harder for a basic relative search.
Alternatively the encoding might not be relative -- there is no technical reason for the encoding to be relative (if there are gaps between encoding values, which can happen for all sorts of reasons* or even the same as the font order, just is common for it to be.
*ASCII for instance has the upper and lower case separated by 20 hex so you can add to go between them ( http://www.asciitable.com/
) as well as the likes of all numbers being 3 and then the number you want. I don't specifically know offhand what Japanese encoding peeps might have done way back when (and my Japanese knowledge is barely enough to hazard a guess as to the possibilities) but there are all sorts of options there which would frustrate such an approach.
You may then have come upon a game for which relative search is not a useful tool; in many cases it is quite useful but not in all of them.