When I looked at OSM for trip planning in Namibia, I simply assumed that the empty spaces on the slippy map meant that the data just wasn't there.
Now, as I try to upload some data, it turns out that it's actually very complete: pretty much all major roads in the country are there!
It's just that they are marked as "highway:tertiary" and "surface:unpaved". Except for a handful of main arteries, all roads in that country are, indeed, unpaved gravel roads, but since you can often drive over 100km/h on them (that's actually the official speed limit, even if it's definitely not always a smart thing to do) and since they're the only way in which cities (by Namibian standards) are interconnected, it's hardly fair to call them tertiary roads...
A nice example is here: http://openstreetmap.com/?lat=-24.426&lon=16.1727&zoom=12&layers=B000FTF
No matter now deep you zoom in, you'll never be able the discover that you're actually looking at the intersection of roads D854 and D850... The labels are never rendered.
In all honesty, those roads don't even show up on Google Maps, but at least it shows the C roads (highest standard gravel roads) in all its glory and some cities.
Also, so other D-roads are tagged as secondary and will show up if you zoom in very closely.
It's probably pretty hard to implement, but a possible solution would be to render detail density adaptive: when there's little or no roads in the area, label roads and mark cities even if they normally wouldn't show up in densly populated area.
As similar example is here: http://openstreetmap.com/?lat=-23.8931&lon=16.0022&zoom=13&layers=B000FTF
Solitaire is a hamlet (as tagged on the map), probably of no more than 100 inhabitants, if that much. But when it's the only place with a shop and gas in an area of, say, a hundred kilometers, it probably makes sense to make it a very prominent hamlet indeed, as is the case on Google Maps:
(Yahoo Maps is far worse then OSM, BTW!)