Is there any iOS offline maps app which also supports searching for an address offline? Is there any iOS map app that works completely without WiFi/3G connection and supports (at a minimum) viewing your current location (on GPS-equipped iOS devices) and searching for an address? My intended use case scenario is mostly navigating around on foot in a foreign city.

I tried Navfree but it seems to require a data connection to search for an address (and is also mostly meant for car navigation). I didn't try Galileo yet, but the website only mentions “online search” for the free version; it's not clear whether the paid version features offline search.
MapsWithMe does that. Available for iPhone/iPad and Android. MapsWithMe Pro for iPhone has offline search. Not an address search though, i.e. you can search for a street, city, restaurant or POI, but not for city+street or street+POI.