Had this problem at a client last week on Outlook Express, changed to smtp.telkomsa.net and it worked - for 2 days!! changed back to smtp.saix.net and it's still OK.
Funny thing, their default mail client is Thunderbird which was fine, they only use OE for Scan to EMail (Brother MFP ControlCentre3 software).