that seems to be correct. The menu items in my eTrex Legend HCx depend on the map I use. With a map generated by mkgmap I get the described behaviour, i.e. I can only "Find nearest". The menu in <Find> <Cities> <Menu button> contains only three options.
On my Garmin etrex venture there are always all four options available, independent of the img-file I choose. With the original mapsource generated files all works as expected. With the maps generated with mkgmap I can select 'Find by name' but only the cities from the basemap are found. If I select 'Find nearest' then all cities are found, also the ones from the osm data. I also asume, that some information is missing. I strongly assume, that this information is contained in the MDR part of the img file. On http://libgarmin.wiki.sourceforge.net/Contribute you can find, that this part contains an search index.