В итоге:
1. Собрал все строки, которые могут быть найдены (получилось около 100 мегабайт).
2. Построил список всех сочетаний из двух букв (aa, ab, ac, ..., zz).
3. Сделал поиск всех сочетаний из пункта 2 в словах из пунтка 1 и сохранил список тех сочетаний, которые не были найдены (ни разу не встречаются). Получилось 165 несуществующих сочетаний.
Теперь ищу в поисковых строках эти несуществующие сочетания. Если что-то найдено, то преобразую запрос в другую раскладку.