Is there any iOS offline maps app which also supports searching for an address offline?
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.