You are correct that availability on one Star Alliance airline does NOT mean it is available on all Star Airlines. It might be available on AC but not UA for example. It has to do with what inventory the airline wishes to release to each Star airline, and how many seats an airline us willing to pay to another airline for a seat. You just have to keep looking. You will love South Africa, but not Johannesburg itself.