Finding housing in Paris is tough for locals. For South African students, it’s a lottery. The South African student does not speak French, is unlikely to have a local garant, has no income in France and is only expected to stay in the country for a couple of years. Easy to see why landlords might choose someone else.
I am no expert, but still, my knowledge may be helpful to my fellow Saffas. Here is a list of of tips and links I wish I had known when I arrived:
CROUS apartments are great. They will be half the price of a normal apartment. But, they are in demand. At Paris 1, each university department has an allocation of rooms. Ask your course administrator for a CROUS room. If there are no rooms left, there is a university wide mailing list of open rooms. You can also go to the CROUS head office and beg for a room. I was there on the morning of Christmas Eve!
Similar to CROUS, is Cité Universitaire has cheap student accommodation. Each building is associated with a nationality. Each building has their own policies and some are easier to join than others.
GarantMe offer an awesome way to get a French garant. And it seems they partner with agencies.
Akelius buy entire buildings in Paris, renovate the building and then rent the rooms at a premium (to recoup the cost of the renovations). My wife and I stayed in two different Akelius apartments and we were very happy. The downside is they are quite expensive and the rooms are unfurnished (but that may be an upside for you).