I am South African and often rent cars in JNB for a day or two on work trips, I've never been hit with an additional fuel charge or fake damage claims. I also never use Avis or Hertz, because they're ridiculously overpriced and have massive queues, whereas Thrifty/Dollar or First Car Rental are usually more affordable, reliable and reputable. I think some of the anonymity of the global operations and franchise model of Avis/Hertz may cause less customer service and accountability.
I rented a car in JNB two weeks ago and noted the rental agreement specified that they refuel all vehicles, regardless of the fuel gauge, and if they need to refuel more than 3 litres they charge you for it, so perhaps that's what happened. Important to note that if you refuel just to the first click, there may be 1-2 litres of space still in the tank, and driving 10-15km could cause the overall space to be >3L. I generally refuel at the airport. Fuel prices in SA are regulated by law and identical in all locations so there is no risk of an airport surcharge or something like you might find in other countries where airport fuel stations charge more.
You get a receipt for a cash fuel purchase, too, you just need to ask for it.