Yo,
I feel you on OSM.. however, one thing I can suggest if you have android, that I know works, and works REALLY well:
On Android, nothing beats Maverick for raw mapping when out of service areas.
It does not do navi well (if at all... dont bother searching, etc)
But for "where am I now?" it is tops.
It gives you a choice of several map sources:
OSM base - Mapnik and OSMa
Google - Maps, sat, hybrid and terrain
Bing - maps sat and hybrid
Wikimapia - Maps, and ovi/nokia, plus the ability to config more
The best part is that so long as you have storage space, it will cache everything you view. So, when I know I will need maps when out of service, I follow the following procedure:
While in service (best done over wifi):
1: Open Maverick and run over where I intend to be.
2: Choose a zoom level deep enough that I can get a general idea of where I am, without too many details (my relation to major roads.. somewhere mid zoom)
3: Scroll around the entire city in that zoom level, caching all the map tiles
4: Go back and zoom deeper in neighborhoods around major areas of interest. I usually cache all tiles showing building outlines within a certain distance of major stations for example
I did this with most of southern Arizona about 2 years ago. I still use those tile caches every time I go home.
Sure, you cant look up an address, but can usually get yourself anywhere. It also helps to add waypoints for any major landmarks before you leave.
You can also download tile packs and covert them as explained here:
http://help.codesector.com/MapsCache