I just went through several hours of trying to setup Kentico to use Microsoft Online Services exchange emal. Finally figured out the setting so thought I would share.

The key is to use the correct port 587

In the US this means your SMTP server in Kentico should be setup up as:
smtp.mail.microsoftonline.com:587

Also the 'from' email must be from a domain that is setup in the microsoft online administration panel. The domain must also be setup as 'authoritative' in microsoft online. I think this just means that all the email for the domain is handled by microsoft.

You might also have to have 'POP' enabled for you specific account you are sending from, but not sure on this part. Microsoft support or the migration tool can assist you in 'enabling' the account for POP / SMTP access. Not sure on this part because the account Im using was already 'pop enabled'.--might not be necessary

Below is the article text that helped me troubleshoot this issue:
Summary
Microsoft Online Services supports sending Simple Mail Transfer Protocol (SMTP) e-mail messages. This article discusses how to configure a SMTP client to connect to Microsoft Online Services SMTP servers to send mail.
More Information
Microsoft Online Services users can send SMTP e-mail messages without any dependencies on the user's legacy e-mail system. SMTP clients can connect to the Microsoft Online Services SMTP servers and authenticate by using Microsoft Online Services user credentails to send e-mail messages. The connection requires Transport Layer Security (TLS).
To connect to the Microsoft Online Services SMTP server, open the SMTP client, and then provide the following information:
• FQDN: The fully qualified domain name (FQDN) of the Microsoft Online Services SMTP server.
The FQDN will be slightly different depending on the Microsoft Online Services data center that the customer's company is connected to. The server FQDNs are listed as follows:
o North America data center: smtp.mail.microsoftonline.com
o Europe, the Middle East, and Africa (EMEA) data center: smtp.mail.emea.microsoftonline.com
o Asia Pacific (APAC) data center: smtp.mail.apac.microsoftonline.com
• User name and password: The user name and password of a Microsoft Online Services user account that has an Exchange Online license.
On most client applications, this setting is located under the My outgoing mail server (SMTP) requires authentication option, which should be selected. Select this option (if it is not already selected). Then, specify your Microsoft Online Services user name and password.
• SMTP port 587: Configure the SMTP port to use port 587.
On most client applications, this setting is configured by using the Server Port Numbers for Outgoing Server (SMTP) option.
• TLS enabled: Make sure that Transport Layer Security (TLS) is enabled in the SMTP client.
On most client applications, this setting is configured by using the My outgoing server (SMTP) requires an encrypted connection (SSL) option. Select this option (if it is not already selected).
Note The From address must use a SMTP domain that is Authoritative. Confirm whether the domain is Authoritative in the Domains area of the Users tab in Microsoft Online Services Administration Center.
Important Update the password of the user's Microsoft Online Services account regularly, before the password expires. If the password expires before it is updated in the SMTP client, SMTP services will stop. Microsoft Online Services passwords expire every 90 days.