Not sure if it's of much help but you could try contacting Telkom and Neotel again, and specifically asking them for WiMax.
Afaik Telkom won't be of much help, they apparently might have stopped doing WiMax and even when they did a lot of Telkom sales/accounts people didn't even know they had it, but there's a chance I guess.
A friend of mine has Neotel WiMax which works ok, I'm not sure if whoever you spoke to at Neotel would have checked on WiMax for you, afaik they only provide "business" WiMax, but I see no reason why you can't get it for private use. I
think he pays something like R1000 a month for uncapped 1mb.
Other than those options you can try searching around for other Wisps (Amobia is a Wisp).
Or if you have any interest in doing a bit of slightly technical stuff (should be fine I reckon if you can build a PC and stuff like that), you can possibly strike a deal with a friend to provide you with internet over wifi. You would have to pay a bit for hardware though, and you would basically need line of sight from where you live to where the other person lives, and they need some sort of internet connection. Also this is technically illegal, but I think that's mainly if it were commercial as you'd need a license.
Or you could just join a Wug, which is a big Wifi network around the city.
http://www.wug.za.net/ that website should point you to everything you need to know about it I think. You wouldn't necessarily get internet that way though (but there are game servers and things running on the network I gather). It's the same kind of hardware needed for the previous suggestion as well.
