Если файл специально преобразуется на компьютере, можно вместе с преобразованным файлом создать индексный файл для пойска. Для j2se это можно было бы сделать с помощью lucene, но lucene слишком сложна для j2me.
Без индексного файла лучше использовать байтовую кодировку. Для используемой кодировки включить файл описания из 1280 байт:
1. 512 байт, 256 char для преобразования в  Unicode
2. 256 байт для приведения к нижнему регистру
3. 256 байт для приведения к верхнему регистру
4. 256 байт для сортировки.
Если используется специальное пробразование файла, эти байты можно добавить в начало файла.
Искомая строка преобразуется в байтовую кодировку (это не быстро, но делается один раз перед поиском).
Чтобы не искать разделители, строки записывать в виде
<длина(1 или 2 байта)>:<строка из соответствующего числа байт>

Если честно, не совсем понял, что подразумевается под байтовой кодировкой и преобразованием искомой строки в байтовую кодировку...
  

Под байтовой кодировкой я подразумевал кодировку в которой символ занимает 1 байт (cp1251, koi8-r), в отличие от utf8, где символ занимает переменное число байт или utf16, где число символов слишком большое, чтобы пользоваться массивами для приведения к верхнему или нижнему регистру.