For some reason using SSL_CTX_new(SSLv23_client_method())
with smtp.live.com always fails and produces the issue presented in my 1st post.
After replacing the client method with SSL_CTX_new(TLSv1_client_method())
, the issue was resolved.
It is weird, why this happens only with this particular server.