http://www.openstreetmap.org/
OpenStreetMap is a free editable map of the whole world. It's a wiki-like map which users can edit. You can upload GPS traces of areas and add street names, etc. Eat your heart out Google Maps.
http://maps.yellowpages.co.za/
Yellow Pages provide the (currently, Jan 08) best available online mapping service for South Africa while Yahoo Maps, Google Maps, etc appear to have no street level data.
