No no no, the filename still comes up in Japanese. That's the weird thing. Everything indicates the system is running in Japanese Unicode except that the patch doesn't run.
I know, but you don't need to have the system using Japanese locale for Japanese characters to display properly since the names of the files are being stored on a filesystem capable of storing the characters in a format the OS can understand.
AFAIK the vpatch (and I believe Touhou itself) is not Unicode-aware, and the error you're getting along with the messed up text that accompanies it is because the characters are being mangled when Windows is converting them from their native codepage (I believe it is CP932) to the computer's current locale. When you use AppLocale a compatibility shim intercepts the function calls responsible for handling text for that program and properly converts them to UTF-16.
To use another example, when I first started playing Touhou on Linux I would get those screwed up filenames even though my machine used Unicode (en_US.UTF-8, for those familiar with locale). Even though everything else was fully capable of handling Japanese characters, the Touhou installer would use Shift_JIS and things would get fucked up. Running the installer with the Japanese locale (ja_JP.UTF-8) made it happy again, ditto for playing the games.
TL;DR: I'm 95% sure that the vpatch is looking for the screwed up name of the EoSD executable because the vpatch itself is having those characters mangled internally.
