As I post this, anyone using Telkom as an ISP is not able to send outgoing emails.
Even if you are not using their mail server.
Telkom is aware of the problem, and currently have no idea when it will be resolved.
I don't know if the problem extends to all ADSL lines, or only ones where Telkom is the ISP.
I've tested via Vodacom, and there's no problem there. The emails go out just fine.