Hetzner
Great value for money, servers are well spec'ed with loads of bandwidth and they provide 50Gb of space on a secondary server for backups. We've been with them for a couple of years now and if you have some requirement, they usually make a plan to try and help you out.
We've never had a price increase (still paying the same as when we signed up), but they do sometimes notify you that "as of next month, you'll now have 50% more bandwidth available". We've gotten that email probably about 3 of 4 times and we currently get 500Gb of bandwidth a month (I think we started off with 50 or 100Gb).
Back when we changed our dedicated server from WebAfrica, I went and researched everyone in SA and Hetzner was by far the best option, but in our case, it is for Windows hosting though.
Alternatively, Afrihost also has Cloud hosting options which might also work for you. Haven't worked with that before, but I'm guessing that they put you on a Virtual server rather than a dedicated server. You'll have to contact them to find out. It may be an option if cost is an issue.
