Created attachment 85755 [details]
sample projects

It is a valid issue.

Attached projects was tested on both 
the NetBeans 6.8M1: 
  Product Version: NetBeans IDE Dev (Build 200908022240)
  Java: 1.6.0_13; Java HotSpot(TM) Client VM 11.3-b02
  System: Windows XP version 5.1 running on x86; Cp1251; ru_RU (nb)
  Userdir: C:\Documents and Settings\vvg\.netbeans\6.8m1
and the a trunk version on the same platform:
  changeset:   141827:01c13dece50c 
  date:        Tue Aug 18 18:24:57 2009 +0200

I confirm that the "Find..." functionality don't work properly when it has been invoked against the attached project
SearchTest_EUC. 

Seems a root cause of the issue is an incorrect value of encoding for the Java source files that is returned after
polling a collection of the service providers registered in the IDE
(service=org.netbeans.spi.queries.FileEncodingQueryImplementation.class)

The NetBeans recognizes encoding of a Java source file as an encoding defined for the project containing that file (in
the test project "SearchTest_EUC" it is "EUC-JP"), but doesn't do it according to the Java Language Specification.
See http://java.sun.com/docs/books/jls/third_edition/html/lexical.html

During the test I've found that the service providers have been polled in the following order:
org.netbeans.modules.versioning.diff.DiffFileEncodingQueryImpl returns null - OK
org.netbeans.modules.versioning.util.queries.DiffFileEncodingQueryImpl returns null - OK
org.netbeans.modules.openide.loaders.DataObjectEncodingQueryImplementation returns null - Not sure that it is OK!
org.netbeans.modules.xml.util.DefaultXmlFileEncodingQueryImpl returns null - OK
org.netbeans.modules.projectapi.ProjectFileEncodingQueryImplementation returns a project encoding "EUC-JP" - OK.
   BTW It also defines a default encoding of the platform as a secondary value that 
       was "windows-1251" on my platform, but it is not used for decoding inside the "Find..." functionality.  
org.netbeans.modules.diff.DiffFileEncodingQueryImplementation returns null - OK

I guess implementation of the DataObjectEncodingQueryImplementation [1] has incorrect behavior, and it should return a
correct encoding value for the Java source file even if containing project defines another encoding. Most likely
encoding of the Java source file should be always UTF-16? 

Probably, a special service provider (service=org.netbeans.spi.queries.FileEncodingQueryImplementation.class)
should be provided for the MIME type "text/x-java", so that it will be accessible via the expression
MimeLookup.getLookup(mimeType).lookup(FileEncodingQueryImplementation.class)
in the method DataObjectEncodingQueryImplementation.getEncoding(FileObject file) - see [2].

[1] 
http://hg.netbeans.org/main/file/2304b0a11dcd/openide.loaders/src/org/netbeans/modules/openide/loaders/DataObjectEncodingQueryImplementation.java#l79
[2]
http://hg.netbeans.org/main/file/2304b0a11dcd/openide.loaders/src/org/netbeans/modules/openide/loaders/DataObjectEncodingQueryImplementation.java#l95

Could you please, review my investigation results and/or reassign the issue if my assumption about
component/subcomponent is wrong.

Sorry, but I think that the problem is somewhere else. I added e.printStackTrace() to catch block on line 712 in
utilities/src/org/netbeans/modules/search/BasicSearchCriteria.java and the following exception is being thrown inside
the corresponding try block:
java.lang.IllegalStateException: Current state = FLUSHED, new state = CODING_END
        at java.nio.charset.CharsetDecoder.throwIllegalStateException(CharsetDecoder.java:951)
        at java.nio.charset.CharsetDecoder.decode(CharsetDecoder.java:537)
        at org.netbeans.api.queries.FileEncodingQuery$ProxyCharset$ProxyDecoder.implFlush(FileEncodingQuery.java:276)
        at java.nio.charset.CharsetDecoder.flush(CharsetDecoder.java:633)
        at org.netbeans.modules.search.Utils.decodeByteBuffer(Utils.java:226)
        at org.netbeans.modules.search.Utils.getCharSequence(Utils.java:180)
        at org.netbeans.modules.search.BasicSearchCriteria.checkFileContent(BasicSearchCriteria.java:710)
        at org.netbeans.modules.search.BasicSearchCriteria.matches(BasicSearchCriteria.java:644)
        at org.netbeans.modules.search.SpecialSearchGroup.processSearchObject(SpecialSearchGroup.java:146)
        at org.netbeans.modules.search.SpecialSearchGroup.doSearch(SpecialSearchGroup.java:119)
        at org.openidex.search.SearchGroup.search(SearchGroup.java:178)
        at org.netbeans.modules.search.SearchTask.run(SearchTask.java:126)
        at org.openide.util.RequestProcessor$Task.run(RequestProcessor.java:602)
        at org.openide.util.RequestProcessor$Processor.run(RequestProcessor.java:1070)

This is (IMO) responsible to the missing occurrence.

Regarding the encoding of the Java files, I think that the Unicode character set is meant as internal representation,
the input file can be in any encoding convertible to Unicode character set (see javac's "-encoding" command line
option). Forcing UTF-16 (or any other encoding) on all Java files would not be correct (note that the files in the
attached project are not UTF-16 encoded files). The project supplied encoding is meant to be used to decode the Java
files (under normal circumstances). Also note that the files from the attached project can be opened in the editor
correctly (by use of the FileEncodingQuery).

It is fixed in the main trunk
http://hg.netbeans.org/main/rev/5ba89a3887a1