Hi Michał
Address search in your map works very well on my device. So maybe it's related to your changes in code or problem lies within content of the index (maybe some characters in other city names are improperly transliterated). Could you send me your mkgmap version?
Its http://www.mkgmap.org.uk/download/mkgmap-sort-r3067.zip There were no changes that were not in that. But I did use a bounds file eg: http://osm2.pleiades.uni-wuppertal.de/bounds/20140128/bounds_20140128.zip which is important to get good search coverage.
BTW - is there any tool to debug those indexes?
There is test.display.MdrDisplay and test.check.MdrCheck in the display project at http://svn.mkgmap.org.uk/display/trunk But there are many false warning, so it is not that useful unless you know what you are looking for. ..Steve