In Internet Explorer, go to Tools > Internet Options > Advanced. Look for SSL options and check the box that says "Use SSL 2.0"
In addition within the Oultook client go to Accounts > Change > More Settings > Advanced tab. Make sure to set to "Auto" on outgoing mail encryption drop down (the options are SSL, TLS, None, Auto).