You can try:
**NaviPOWM**: offline Maps that are renderes by vectors
**Gosmore**: very fast vector display, also search fution included
**[MapFactor Navigator Free][1]** is a navigation solution with search function, running also on Windows or Linux (via Wine)
**GpsMid**: also offline and vector map ... originally for JavaME devices, but you can run it with [microemu][2] on any desktop PC with Java (increase screen size of the emulated device!) ... new release with house number searching.
**gpsVP**: also offline, for OSM maps or Garmin maps.
**Navit**: also with navigation features, but but not so easy to configure due to the famous file navit.xml
**MoNav**: still in early development, but very promising
Also have a look at the OSM wiki for programs that store theit map data offline at [Software][3]
When you have detailed questions about a programm or the map source for them, come to [OSM forum][4].
[1]: http://wiki.openstreetmap.org/wiki/MapFactor_Navigator_Free
[2]: http://www.microemu.org
[3]: http://wiki.openstreetmap.org/wiki/Software
[4]: http://forum.osm.org
