It seems that use locale just doesn't work well for UNICODE character sets, because it doesn't consider these locale-specific characters valid word characters. I think it's a problem in Perl, because clearly \w should include "צהו" Scandinavian characters when such a locale is in effect, UNICODE or not.

But well, I can avoid buggy locale handling by explicitly converting all input and output to UNICODE, regardless of the user's settings. I just wish it would have worked...