Comprehensive database of all cities/towns in South Africa?

There is always geonames though I have no idea how comprehensive their South Africa data is.

Another option might be the South African Statistics agency

I put a list online a while back of a number of free GIS datasets (see http://freegisdata.rtwilson.com/). Two that may be relevant to you are:

• Natural Earth populated places - although this is likely to only have fairly large places in it (available at http://www.naturalearthdata.com/downloads/10m-cultural-vectors/)
• NGIS Country Geoname Files - a list of names of regions, areas and populated places for each country in the world, provided by the US Government (available at http://earth-info.nga.mil/gns/html/namefiles.htm)

MapIT have South African Datasets including Towns/Cities (POI) - It is usually derived from TeleAtlas (Owned by TomTom) so likely to be costly.

http://www.map-it.co.za/about/index.html

From the Press Release: June 2011

"Given these trends, MapIT, Southern Africa’s leading enabler of technological mapping solutions, is concentrating on supplying accurate, current, enriched data by adding Points of Interest (POI) to the data."