f0dder:
OK, so everything I know at the moment:
1. Console in Windows XP can produce full Unicode output but only for displaying. Piping and redirecting is unsupported so it's useless for us.
2. Standard printing functions like wprintf (used in locate.exe) uses built-in WideCharToMultibyte conversion (to DOS codepage in my case), so polish letters have wrong hexcodes in normal windows.
3. I'm able to write raw Unicode to console (swprintf+WriteFile, without widechar->codepage conversion) - when displaying it look like there are spaces between all letters, but after redirecting to a file it works like a charm (even without BOM :) ).

So everything we need now is widechar implementation of Locate plug-in. I don't have Delphi so I can't play with that :( Anybody have seen Okke recently? Maybe you have enough time to make plug-in with integrated Locate :)

Armando:
I think it's unresolvable at the moment. We have to wait for fixes or full Unicode version of this plug-in.

@f0dder:
Unfortunately I'm not  sure how does this stupid console work :(
I think you are right about redirection detection. Look at http://blogs.msdn.com/junfeng/archive/2004/02/25/79621.aspx. That's exactly the same thing you said:) I used that example in my testapp.

Can you redirect your output to a file (if it'll work at all) and then open it using notepad? In my case displaying using WriteConsoleW and WriteFile works fine but redirection works only with WriteFile (WriteConsoleW gives 0-byte file). But when I open created file with notepad I still get messed Unicode characters :(

I think that Locate should provide option to directly write results to a file (without console and redirection) or simple library interface for searching.