sygic, ovi maps, and wayfinder all have offline maps, whivh is great.
ovi needs a connection to perform a search though, althpugh the online search is good - also does not let you save any POIs or favorites either, the only way is to create a contact with an address which is bizarre, and a bigger ommision than the lack of turn by turn.
wayfinder does have full address searching including street name. it then allows to save the found address as a favorite for navigation too later.

both ovi maps and sygic have abysmal user interfaces, wayfinder's wasnt great but was/is the least terrible. Oh and sygic has less than stellar stability.

this wasn't supposed to turn into a comparison review, but more a lament about the dumbing down and simplification of these programs to the point where useful functionality is dumped to make the ui as simple and as pretty as possible.