Thanks to the answers to this question and related questions on this site, I found and wound up trying three different offline map apps which also support offline search. All three offer the basic features of downloading maps for a certain region, viewing your current location and searching for nearby street names and points of interest. In addition, OffMaps 2 and City Maps 2Go also feature downloadable Wikipedia articles for the points of interest on each map. Offmaps 2 can also show a public transport network overlay on top of the regular map.
- MapsWithMe Pro: €3.99 for the app, no extra charges per map.
- OffMaps 2: €0.79 for the app, includes 2 free maps; €0.79 per pack of 3 extra maps or €4.99 for unlimited maps. Each map includes Wikipedia articles (optional download) and a public transport overlay.
- City Maps 2Go: €1.59 for the app, no extra charges per map. Enabling the Wikipedia articles download option is an additional one-time €2.39 charge. (*)
Based upon first impressions, the one I would recommend is City Maps 2Go. The public transport overlay of OffMaps 2 is an interesting additional feature, but I prefer City Maps 2Go's cleaner interface. I also already experienced several app crashes with OffMaps 2. MapsWithMe Pro seems comparatively expensive.
(*) The app appears to be designed to charge a separate fee for enabling this option for each map, but currently has an “Introduction offer: buy ‘Wiki Plus’ now and you will get lifetime, global, unlimited download rights.”