Пример

public static void main( String[] args ) {
String str = "ABC\ud800\udc00"; //\ud800\udc00 = U+10000 //$NON-NLS-1$
int index = str.indexOf( 0x10000 );
if ( index == -1 ) {
System.out.println("Строка не поддерживает дополнительные символы."); //$NON-NLS-1$
} else {
System.out.println("Index = " + index); //$NON-NLS-1$
}
}

public static void TestIndexOf() {
String str = "A\u0300";
int index = str.indexOf(A);
if (index == -1 ) {
System.out.println("OK!");
} else {
System.out.println("Символ 'A' не должен соответствовать A\\u0300");
}
}

public static void TestIndexOf() {
String str = "Съешь ещё этих мягких французских булок, да выпей же чаю.";
int index = str.indexOf("FOX");
if (index == -1 ) {
System.out.println("IndexOf не поддерживает сравнение с учетом локали.");
} else {
System.out.println("OK!");
}
}

Решение

Используйте ICU 2.6.1com.ibm.icu.text.StringSearch, обратитесь к документации StringSearch Java Doc

public static void main( String[] args ) {
RuleBasedCollator coll = (RuleBasedCollator)Collator.getInstance(Locale.US);
coll.setStrength(Collator.PRIMARY);
com.ibm.icu.text.StringSearch search = new com.ibm.icu.text.StringSearch("FOX", new StringCharacterIterator("Съешь ещё этих мягких французских булок, да выпей же чаю."), coll); //$NON-NLS-1$ //$NON-NLS-2$
int index = search.first();
System.out.println("Index = " + index); //$NON-NLS-1$
}